Submission #127981

#TimeUsernameProblemLanguageResultExecution timeMemory
127981aintaDragon 2 (JOI17_dragon2)C++17
100 / 100
1165 ms18896 KiB
#include<cstdio> #include<algorithm> #include<vector> #define pii pair<int,int> using namespace std; struct point { long long x, y; int num; point operator +(const point &p)const { return { x + p.x,y + p.y }; } point operator -(const point &p)const { return { x - p.x,y - p.y }; } int dir() const { if (x > 0 || (x >= 0 && y > 0))return 0; return 1; } bool operator <(const point &p)const { if (dir() != p.dir())return dir() < p.dir(); return y * p.x < p.y*x; } }w[30100], ori[30100], A, B; long long ccw(point a, point b, point c) { return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x); } int Col[30100]; int n, K; struct AA { int x, y; }P[30100]; struct Rect { int bx, by, ex, ey; }R[30100]; void Make(point O, int ck) { int i; vector<point>T; for (i = 1; i <= n + 1; i++) { point t1 = w[i] - O; t1.num = i; point t2 = O - w[i]; t2.num = -i; T.push_back(t1); T.push_back(t2); } sort(T.begin(), T.end()); int sz = T.size(), pv = 0, pv2 = 0; for (i = 0; i < sz; i++) { if (T[i].num == -(n + 1)) { pv = i; } if (T[i].num == n + 1)pv2 = i; } for (i = 0; i < sz; i++) { int t = T[(pv + i) % sz].num; if (abs(t) > n)continue; if (t > 0) { if (!ck)P[t].x = R[t].bx = i + 1; else P[t].y = R[t].by = i + 1; } else { t = -t; if (!ck)R[t].ex = i + 1; else R[t].ey = i + 1; } } } int Q; const int SZ = 65536; int BIT[SZ]; const int TH = 150; void Add(int a, int b) { while (a < SZ) { BIT[a] += b; a += (a&-a); } } int Sum(int a) { int r = 0; while (a) { r += BIT[a]; a -= (a&-a); } return r; } struct Seg { int x, b, e, ck; bool operator<(const Seg &p)const { return x < p.x; } }U[SZ]; pii PP[SZ]; vector<int>G[30100]; int Query(int a, int b) { int i, c1 = 0, c2 = 0; for (auto &t : G[a]) { U[c1++] = { R[t].bx,R[t].by,R[t].ey,1 }; U[c1++] = { R[t].ex + 1,R[t].by,R[t].ey,-1 }; } for (auto &t : G[b]) { PP[c2++] = { P[t].x, P[t].y }; } sort(U, U + c1); sort(PP, PP + c2); int res = 0, pv = 0; for (i = 0; i < c2; i++) { while (pv < c1 && U[pv].x <= PP[i].first) { Add(U[pv].b, U[pv].ck); Add(U[pv].e + 1, -U[pv].ck); pv++; } res += Sum(PP[i].second); } while (pv > 0) { pv--; Add(U[pv].b, -U[pv].ck); Add(U[pv].e + 1, U[pv].ck); } return res; } int D1[210][30100], D2[210][30100], D[30100], Num[30100]; struct BBB { int x, y, col; bool operator<(const BBB &p)const { return x < p.x; } }PPP[SZ]; void PreCalc1(int col) { int i; for (i = 1; i <= K; i++)D[i] = 0; int c1 = 0, c2 = 0; for (auto &t : G[col]) { U[c1++] = { R[t].bx,R[t].by,R[t].ey,1 }; U[c1++] = { R[t].ex + 1,R[t].by,R[t].ey,-1 }; } for (i = 1; i <= n; i++) PPP[c2++] = { P[i].x,P[i].y,Col[i] }; sort(U, U + c1); sort(PPP, PPP + c2); int res = 0, pv = 0; for (i = 0; i < c2; i++) { while (pv < c1 && U[pv].x <= PPP[i].x) { Add(U[pv].b, U[pv].ck); Add(U[pv].e + 1, -U[pv].ck); pv++; } D[PPP[i].col] += Sum(PPP[i].y); } while (pv > 0) { pv--; Add(U[pv].b, -U[pv].ck); Add(U[pv].e + 1, U[pv].ck); } } void PreCalc2(int col) { int i; for (i = 1; i <= K; i++)D[i] = 0; int c1 = 0, c2 = 0; for (i = 1; i <= n; i++) { U[c1++] = { R[i].bx - 1, R[i].by, R[i].ey, -Col[i] }; U[c1++] = { R[i].ex, R[i].by, R[i].ey, Col[i] }; } for (auto &t : G[col]) { PP[c2++] = { P[t].x, P[t].y }; } sort(U, U + c1); sort(PP, PP + c2); int pv = 0; for (i = 0; i < c1; i++) { while (pv < c2 && PP[pv].first <= U[i].x) { Add(PP[pv].second, 1); pv++; } int t = Sum(U[i].e) - Sum(U[i].b - 1); if (U[i].ck > 0) { D[U[i].ck] += t; } else { D[-U[i].ck] -= t; } } for (i = 0; i < SZ; i++)BIT[i] = 0; } int main() { int i, a, b, j; scanf("%d%d", &n, &K); for (i = 1; i <= n; i++) { scanf("%lld%lld%d", &w[i].x, &w[i].y, &Col[i]); G[Col[i]].push_back(i); w[i].num = i; } scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y); w[n + 1] = B; Make(A, 0); w[n + 1] = A; Make(B, 1); for (i = 1; i <= n; i++) { if (R[i].ex < R[i].bx)swap(R[i].bx, R[i].ex); if (R[i].ey < R[i].by)swap(R[i].by, R[i].ey); } int cc = 0; for (i = 1; i <= K; i++) { if (G[i].size() > TH) { Num[i] = ++cc; PreCalc1(i); for (j = 1; j <= K; j++)D1[cc][j] = D[j]; PreCalc2(i); for (j = 1; j <= K; j++)D2[cc][j] = D[j]; } } scanf("%d", &Q); while (Q--) { scanf("%d%d", &a, &b); if (G[b].size() > TH) { printf("%d\n", D2[Num[b]][a]); } else if (G[a].size() > TH) { printf("%d\n", D1[Num[a]][b]); } else { printf("%d\n", Query(a, b)); } } }

Compilation message (stderr)

dragon2.cpp: In function 'void Make(point, int)':
dragon2.cpp:45:29: warning: variable 'pv2' set but not used [-Wunused-but-set-variable]
  int sz = T.size(), pv = 0, pv2 = 0;
                             ^~~
dragon2.cpp: In function 'void PreCalc1(int)':
dragon2.cpp:138:6: warning: unused variable 'res' [-Wunused-variable]
  int res = 0, pv = 0;
      ^~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:187:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &K);
  ~~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%d", &w[i].x, &w[i].y, &Col[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:193:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:212:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
dragon2.cpp:214:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...