Submission #49664

#TimeUsernameProblemLanguageResultExecution timeMemory
49664gs14004Circle selection (APIO18_circle_selection)C++17
100 / 100
3570 ms231144 KiB
#include<cstdio> #include<algorithm> #define N_ 301000 using namespace std; struct Circle { int x, y, r, num; bool operator<(const Circle &p)const { return r != p.r ? r > p.r:num < p.num; } }w[N_]; int n, Res[N_], INF = 1e9, U[22][1<<21], UF[N_*4][22]; struct point { int x, y, num; bool operator<(const point &p)const { return x != p.x ? x < p.x : y < p.y; } }P[N_*4]; bool Intersect(int a, int b) { long long dx = w[a].x - w[b].x, dy = w[a].y - w[b].y, dr = w[a].r + w[b].r; if (dx*dx + dy*dy <= dr*dr)return true; return false; } void Chk(int a, int b) { if (Res[w[b].num])return; if (Intersect(a, b))Res[w[b].num] = w[a].num; } int Find(int a, int pv) { if (a == UF[a][pv])return a; return UF[a][pv] = Find(UF[a][pv], pv); } void Del(int a, int pv) { UF[a][pv] = Find(UF[a + 1][pv], pv); } void Do2(int a, int nd, int pv) { int bb; int y1 = w[a].y - w[a].r, y2 = w[a].y + w[a].r; if (pv >= 3) { int b = (nd << pv), e = ((nd + 1) << pv) - 1; bb = e + 1; int mid; while (b <= e) { mid = (b + e) >> 1; if (P[U[pv][mid]].y >= y1) { bb = mid; e = mid - 1; } else b = mid + 1; } } else { bb = (nd << pv); } int e = ((nd + 1) << pv); while (1) { bb = Find(bb, pv); if (bb >= e)break; int t = U[pv][bb]; if (P[t].y > y2)break; int tt = P[t].num; Chk(a, tt); if (Res[w[tt].num])Del(bb, pv); bb++; } } void Do(int a, int b, int e) { int pv = 0; while (b <= e) { if (b & 1) { Do2(a, b, pv); } if (!(e & 1)) { Do2(a, e, pv); } b = (b + 1) >> 1; e = (e - 1) >> 1; pv++; } } void Go(int a, int bx, int ex, int by, int ey) { point tp = { bx,-INF * 2 - 1, -1 }; int b = lower_bound(P + 1, P + n * 4 + 1, tp) - P; tp = { ex + 1, -INF * 2 - 1, -1 }; int e = lower_bound(P + 1, P + n * 4 + 1, tp) - P - 1; Do(a, b - 1, e - 1); } int main() { int i, j; scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r); w[i].num = i; } sort(w + 1, w + n + 1); for (i = 1; i <= n; i++) { P[i] = { w[i].x - w[i].r,w[i].y - w[i].r,i }; P[i+n] = { w[i].x - w[i].r,w[i].y + w[i].r,i }; P[i+n+n] = { w[i].x + w[i].r,w[i].y - w[i].r,i }; P[i+n+n+n] = { w[i].x + w[i].r,w[i].y + w[i].r,i }; } sort(P + 1, P + n*4 + 1); for (i = 0; i < n * 4; i++) { U[0][i] = i + 1; } for (i = 0; i < 20; i++) { for (j = 0; j < n * 4; j += (1 << (i + 1))) { int mid = j + (1 << i), ed = j + (1 << (i + 1)); int p1 = j, p2 = mid, pv = j; while (p1 < mid || p2 < ed) { if (p2 == ed || (p1 != mid && P[U[i][p1]].y < P[U[i][p2]].y)) { U[i + 1][pv++] = U[i][p1++]; } else { U[i + 1][pv++] = U[i][p2++]; } } } } for (i = 0; i <= n * 4 + 10; i++) { for (j = 0; j <= 20; j++)UF[i][j] = i; } for (i = 1; i <= n; i++) { if (Res[w[i].num])continue; Res[w[i].num] = w[i].num; Go(i, w[i].x - w[i].r, w[i].x + w[i].r, w[i].y - w[i].r, w[i].y + w[i].r); } for (i = 1; i <= n; i++)printf("%d ", Res[i]); }

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
circle_selection.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...