백준 온라인 저지 - 16336. Points and Rectangles
- 공유 링크 만들기
- 이메일
- 기타 앱
백준 온라인 저지 - 16336. Points and Rectangles
#include using namespace std; typedef long long ll; #define ALL(x) (x).begin(), (x).end() #define NTH(v, x) ((int) (lower_bound(ALL(v), (x)) - (v).begin())) #define UNIQUE(v) v.erase(unique(ALL(v)), (v).end()) const int MAX_Q = 1e5 + 20, MAX_Q2 = MAX_Q*2, MAX_Q4 = MAX_Q*4; namespace FW { ll F[MAX_Q2]; void add(int p, int v) { for (p+=10; p to_tuple() const { return make_tuple(idx, x, y); } bool operator<(const query &o;) const { return to_tuple() < o.to_tuple(); } } Qu[MAX_Q4], T[MAX_Q4]; int Q, Qulen; vector Cx, Cy; int Xsz, Ysz; ll Ans[MAX_Q]; void CDQ1(int l, int r) { // 직사각형을 추가하는 쿼리 if (l == r) return; int m = (l + r) / 2; CDQ1(l, m); CDQ1(m+1, r); int p1 = l, p2 = m+1, p = l; while (p1 <= m && p2 <= r) { if (Qu[p1].x <= Qu[p2].x) { if (Qu[p1].w == 0) { FW::add(Qu[p1].y, 1); } T[p++] = Qu[p1++]; } else { if (Qu[p2].w != 0) { Ans[Qu[p2].idx] += FW::sum(Qu[p2].y) * Qu[p2].w; } T[p++] = Qu[p2++]; } } int bp1 = p1; while (p1 <= m) T[p++] = Qu[p1++]; while (p2 <= r) { if (Qu[p2].w != 0) { Ans[Qu[p2].idx] += FW::sum(Qu[p2].y) * Qu[p2].w; } T[p++] = Qu[p2++]; } for (int i=l; i= l && p2 >= m+1) { if (Qu[p1].x >= Qu[p2].x) { if (Qu[p1].w != 0) { FW::add(Qu[p1].y, Qu[p1].w); } T[p--] = Qu[p1--]; } else { if (Qu[p2].w == 0) { Ans[Qu[p2].idx] += FW::sum(Qu[p2].y, Ysz+1); } T[p--] = Qu[p2--]; } } int bp1 = p1; while (p1 >= l) { T[p--] = Qu[p1--]; } while (p2 >= m+1) { if (Qu[p2].w == 0) { Ans[Qu[p2].idx] += FW::sum(Qu[p2].y, Ysz+1); } T[p--] = Qu[p2--]; } for (int i=m; i>bp1; i--) { if (Qu[i].w != 0) { FW::add(Qu[i].y, -Qu[i].w); } } for (int i=l; i<=r; i++) { Qu[i] = T[i]; } } int main() { scanf("%d", &Q;); for (int q=1; q<=Q; q++) { int ty; scanf("%d", &ty;); if (ty == 1) { int x, y; scanf("%d%d", &x;, &y;); Qu[++Qulen] = query(q, x, y); Cx.push_back(x); Cy.push_back(y); } else { int xs, ys, xf, yf; scanf("%d%d%d%d", &xs;, &ys;, &xf;, &yf;); Qu[++Qulen] = query(q, xs-1, ys-1, 1); Qu[++Qulen] = query(q, xf, yf, 1); Qu[++Qulen] = query(q, xs-1, yf, -1); Qu[++Qulen] = query(q, xf, ys-1, -1); Cx.push_back(xs-1); Cx.push_back(xf); Cy.push_back(ys-1); Cy.push_back(yf); } } sort(ALL(Cx)); sort(ALL(Cy)); UNIQUE(Cx); UNIQUE(Cy); Xsz = Cx.size(); Ysz = Cy.size(); for (int q=1; q<=Qulen; q++) { Qu[q].x = 1 + NTH(Cx, Qu[q].x); Qu[q].y = 1 + NTH(Cy, Qu[q].y); } sort(Qu+1, Qu+1+Qulen); CDQ1(1, Qulen); sort(Qu+1, Qu+1+Qulen); CDQ2(1, Qulen); for (int i=1; i<=Q; i++) { Ans[i] += Ans[i-1]; printf("%lld
", Ans[i]); } }
from http://lego0901.tistory.com/20 by ccl(A) rewrite - 2020-03-16 20:54:08
- 공유 링크 만들기
- 이메일
- 기타 앱
댓글
댓글 쓰기