#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
struct node{
int id, mn[2];
node *l, *r;
node(int i) { l = r = NULL; id = i; }
};
int p[N][2],A[N],B[N],tmp[N],R[N],ans[N],r;
node* bld(int l, int r, int k){
if(l > r) return NULL;
int *X = k ? B : A;
int *Y = k ? A : B;
int i,j,jj, m = l+r >> 1;
int mid = p[ X[m] ][k];
for(; m>l && mid == p[ X[m-1] ][k] ; m--);
node *root = new node(X[m]);
root->mn[0] = A[l];
root->mn[1] = B[l];
for(j=l-1,jj=m,i=l;i<=r;i++){
if(p[ Y[i] ][k] < mid)
tmp[++j] = Y[i];
else if(Y[i] != X[m])
tmp[++jj] = Y[i];
}
for(i=l;i<=r;i++) Y[i] = tmp[i];
root -> l = bld(l,m-1,!k);
root -> r = bld(m+1,r,!k);
return root;
}
node* del(node* root, int i, int k){
if(root == NULL) assert(0);
if(root->id == i){
if(root -> r != NULL){
int j = root->r->mn[k];
root->id = j;
root->r = del(root->r, j, !k);
}
else if(root -> l != NULL){
int j = root->l->mn[k];
root->id = j; root->r = root->l; root->l = NULL;
root->r = del(root->r, j, !k);
}
else return NULL;
}
else{
if(p[i][k] < p[ root->id ][k]) root->l = del(root->l, i, !k);
else root->r = del(root->r, i, !k);
}
root->mn[k] = root->l ? root->l->mn[k] : root->id;
root->mn[!k] = root->id;
if(root->l != NULL && p[ root->l->mn[!k] ][!k] < p[ root->mn[!k] ][!k]) root->mn[!k] = root->l->mn[!k];
if(root->r != NULL && p[ root->r->mn[!k] ][!k] < p[ root->mn[!k] ][!k]) root->mn[!k] = root->r->mn[!k];
return root;
}
vector < int > era;
void f(node* root, int q[], int k){
if(root == NULL) return;
ll a = q[0] - p[ root->id ][0];
ll b = q[1] - p[ root->id ][1];
ll c = R[ root->id ];
if(a*a + b*b <= (r+c)*(r+c))
era.pb(root->id);
int t = p[ root->id ][k];
if(q[k] < t){
f(root->l,q,!k);
if(t - q[k] <= r+r) f(root->r,q,!k);
}
else{
f(root->r,q,!k);
if(q[k] - t <= r+r) f(root->l,q,!k);
}
}
int h;
bool cmp(int i, int j){
return p[i][h] < p[j][h];
}
map < pp , int > M;
int n,i,j;
pp T[N];
int main()
{
cin >> n;
for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i;
if(M[ mp(p[i][0] , p[i][1]) ]++ == 30) assert(0);
}
h=0; sort(A+1,A+n+1,cmp);
h=1; sort(B+1,B+n+1,cmp);
node *root = bld(1,n,0);
for(i=1;i<=n;i++) T[i] = mp(-R[i] , i);
sort(T+1 , T+n+1);
for(i=1;i<=n;i++){
int id = T[i].nd;
if(ans[id]) continue;
era.clear();
r = R[id];
f(root , p[id], 0);
for(auto j : era){
ans[j] = id;
root = del(root, j, 0);
}
}
for(i=1;i<=n;i++) printf("%d ", ans[i]);
return 0;
}
Compilation message
circle_selection.cpp: In function 'node* bld(int, int, int)':
circle_selection.cpp:26:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int i,j,jj, m = l+r >> 1;
~^~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:101:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
448 KB |
Output is correct |
4 |
Correct |
2 ms |
524 KB |
Output is correct |
5 |
Correct |
3 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
616 KB |
Output is correct |
8 |
Correct |
2 ms |
616 KB |
Output is correct |
9 |
Correct |
3 ms |
616 KB |
Output is correct |
10 |
Correct |
2 ms |
616 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
2 ms |
620 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
4 ms |
748 KB |
Output is correct |
17 |
Correct |
4 ms |
748 KB |
Output is correct |
18 |
Correct |
4 ms |
820 KB |
Output is correct |
19 |
Correct |
11 ms |
1388 KB |
Output is correct |
20 |
Correct |
14 ms |
1388 KB |
Output is correct |
21 |
Correct |
11 ms |
1404 KB |
Output is correct |
22 |
Correct |
13 ms |
1420 KB |
Output is correct |
23 |
Correct |
12 ms |
1436 KB |
Output is correct |
24 |
Correct |
13 ms |
1436 KB |
Output is correct |
25 |
Correct |
13 ms |
1456 KB |
Output is correct |
26 |
Correct |
14 ms |
1456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
803 ms |
47352 KB |
Output is correct |
2 |
Correct |
816 ms |
47352 KB |
Output is correct |
3 |
Correct |
774 ms |
47352 KB |
Output is correct |
4 |
Correct |
772 ms |
47544 KB |
Output is correct |
5 |
Correct |
751 ms |
47544 KB |
Output is correct |
6 |
Correct |
955 ms |
47544 KB |
Output is correct |
7 |
Correct |
844 ms |
47544 KB |
Output is correct |
8 |
Correct |
943 ms |
47544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
47544 KB |
Output is correct |
2 |
Correct |
356 ms |
47544 KB |
Output is correct |
3 |
Correct |
1131 ms |
47544 KB |
Output is correct |
4 |
Correct |
1230 ms |
47544 KB |
Output is correct |
5 |
Correct |
1237 ms |
47544 KB |
Output is correct |
6 |
Correct |
603 ms |
47544 KB |
Output is correct |
7 |
Correct |
252 ms |
47544 KB |
Output is correct |
8 |
Correct |
40 ms |
47544 KB |
Output is correct |
9 |
Correct |
1310 ms |
47544 KB |
Output is correct |
10 |
Correct |
1223 ms |
47544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1250 ms |
47544 KB |
Output is correct |
2 |
Correct |
1057 ms |
47544 KB |
Output is correct |
3 |
Correct |
919 ms |
47544 KB |
Output is correct |
4 |
Correct |
1312 ms |
47544 KB |
Output is correct |
5 |
Correct |
1106 ms |
47544 KB |
Output is correct |
6 |
Correct |
937 ms |
47544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
448 KB |
Output is correct |
4 |
Correct |
2 ms |
524 KB |
Output is correct |
5 |
Correct |
3 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
616 KB |
Output is correct |
8 |
Correct |
2 ms |
616 KB |
Output is correct |
9 |
Correct |
3 ms |
616 KB |
Output is correct |
10 |
Correct |
2 ms |
616 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
2 ms |
620 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
4 ms |
748 KB |
Output is correct |
17 |
Correct |
4 ms |
748 KB |
Output is correct |
18 |
Correct |
4 ms |
820 KB |
Output is correct |
19 |
Correct |
11 ms |
1388 KB |
Output is correct |
20 |
Correct |
14 ms |
1388 KB |
Output is correct |
21 |
Correct |
11 ms |
1404 KB |
Output is correct |
22 |
Correct |
13 ms |
1420 KB |
Output is correct |
23 |
Correct |
12 ms |
1436 KB |
Output is correct |
24 |
Correct |
13 ms |
1436 KB |
Output is correct |
25 |
Correct |
13 ms |
1456 KB |
Output is correct |
26 |
Correct |
14 ms |
1456 KB |
Output is correct |
27 |
Correct |
18 ms |
47544 KB |
Output is correct |
28 |
Correct |
20 ms |
47544 KB |
Output is correct |
29 |
Correct |
18 ms |
47544 KB |
Output is correct |
30 |
Correct |
27 ms |
47544 KB |
Output is correct |
31 |
Correct |
24 ms |
47544 KB |
Output is correct |
32 |
Correct |
23 ms |
47544 KB |
Output is correct |
33 |
Correct |
270 ms |
47544 KB |
Output is correct |
34 |
Correct |
270 ms |
47544 KB |
Output is correct |
35 |
Correct |
331 ms |
47544 KB |
Output is correct |
36 |
Correct |
304 ms |
47544 KB |
Output is correct |
37 |
Correct |
361 ms |
47544 KB |
Output is correct |
38 |
Correct |
354 ms |
47544 KB |
Output is correct |
39 |
Correct |
510 ms |
47544 KB |
Output is correct |
40 |
Correct |
526 ms |
47544 KB |
Output is correct |
41 |
Correct |
367 ms |
47544 KB |
Output is correct |
42 |
Correct |
264 ms |
47544 KB |
Output is correct |
43 |
Correct |
312 ms |
47544 KB |
Output is correct |
44 |
Correct |
235 ms |
47544 KB |
Output is correct |
45 |
Correct |
249 ms |
47544 KB |
Output is correct |
46 |
Correct |
296 ms |
47544 KB |
Output is correct |
47 |
Correct |
302 ms |
47544 KB |
Output is correct |
48 |
Correct |
299 ms |
47544 KB |
Output is correct |
49 |
Correct |
282 ms |
47544 KB |
Output is correct |
50 |
Correct |
293 ms |
47544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
448 KB |
Output is correct |
4 |
Correct |
2 ms |
524 KB |
Output is correct |
5 |
Correct |
3 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
616 KB |
Output is correct |
8 |
Correct |
2 ms |
616 KB |
Output is correct |
9 |
Correct |
3 ms |
616 KB |
Output is correct |
10 |
Correct |
2 ms |
616 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
2 ms |
620 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
4 ms |
748 KB |
Output is correct |
17 |
Correct |
4 ms |
748 KB |
Output is correct |
18 |
Correct |
4 ms |
820 KB |
Output is correct |
19 |
Correct |
11 ms |
1388 KB |
Output is correct |
20 |
Correct |
14 ms |
1388 KB |
Output is correct |
21 |
Correct |
11 ms |
1404 KB |
Output is correct |
22 |
Correct |
13 ms |
1420 KB |
Output is correct |
23 |
Correct |
12 ms |
1436 KB |
Output is correct |
24 |
Correct |
13 ms |
1436 KB |
Output is correct |
25 |
Correct |
13 ms |
1456 KB |
Output is correct |
26 |
Correct |
14 ms |
1456 KB |
Output is correct |
27 |
Correct |
803 ms |
47352 KB |
Output is correct |
28 |
Correct |
816 ms |
47352 KB |
Output is correct |
29 |
Correct |
774 ms |
47352 KB |
Output is correct |
30 |
Correct |
772 ms |
47544 KB |
Output is correct |
31 |
Correct |
751 ms |
47544 KB |
Output is correct |
32 |
Correct |
955 ms |
47544 KB |
Output is correct |
33 |
Correct |
844 ms |
47544 KB |
Output is correct |
34 |
Correct |
943 ms |
47544 KB |
Output is correct |
35 |
Correct |
2 ms |
47544 KB |
Output is correct |
36 |
Correct |
356 ms |
47544 KB |
Output is correct |
37 |
Correct |
1131 ms |
47544 KB |
Output is correct |
38 |
Correct |
1230 ms |
47544 KB |
Output is correct |
39 |
Correct |
1237 ms |
47544 KB |
Output is correct |
40 |
Correct |
603 ms |
47544 KB |
Output is correct |
41 |
Correct |
252 ms |
47544 KB |
Output is correct |
42 |
Correct |
40 ms |
47544 KB |
Output is correct |
43 |
Correct |
1310 ms |
47544 KB |
Output is correct |
44 |
Correct |
1223 ms |
47544 KB |
Output is correct |
45 |
Correct |
1250 ms |
47544 KB |
Output is correct |
46 |
Correct |
1057 ms |
47544 KB |
Output is correct |
47 |
Correct |
919 ms |
47544 KB |
Output is correct |
48 |
Correct |
1312 ms |
47544 KB |
Output is correct |
49 |
Correct |
1106 ms |
47544 KB |
Output is correct |
50 |
Correct |
937 ms |
47544 KB |
Output is correct |
51 |
Correct |
18 ms |
47544 KB |
Output is correct |
52 |
Correct |
20 ms |
47544 KB |
Output is correct |
53 |
Correct |
18 ms |
47544 KB |
Output is correct |
54 |
Correct |
27 ms |
47544 KB |
Output is correct |
55 |
Correct |
24 ms |
47544 KB |
Output is correct |
56 |
Correct |
23 ms |
47544 KB |
Output is correct |
57 |
Correct |
270 ms |
47544 KB |
Output is correct |
58 |
Correct |
270 ms |
47544 KB |
Output is correct |
59 |
Correct |
331 ms |
47544 KB |
Output is correct |
60 |
Correct |
304 ms |
47544 KB |
Output is correct |
61 |
Correct |
361 ms |
47544 KB |
Output is correct |
62 |
Correct |
354 ms |
47544 KB |
Output is correct |
63 |
Correct |
510 ms |
47544 KB |
Output is correct |
64 |
Correct |
526 ms |
47544 KB |
Output is correct |
65 |
Correct |
367 ms |
47544 KB |
Output is correct |
66 |
Correct |
264 ms |
47544 KB |
Output is correct |
67 |
Correct |
312 ms |
47544 KB |
Output is correct |
68 |
Correct |
235 ms |
47544 KB |
Output is correct |
69 |
Correct |
249 ms |
47544 KB |
Output is correct |
70 |
Correct |
296 ms |
47544 KB |
Output is correct |
71 |
Correct |
302 ms |
47544 KB |
Output is correct |
72 |
Correct |
299 ms |
47544 KB |
Output is correct |
73 |
Correct |
282 ms |
47544 KB |
Output is correct |
74 |
Correct |
293 ms |
47544 KB |
Output is correct |
75 |
Correct |
1010 ms |
47544 KB |
Output is correct |
76 |
Correct |
1027 ms |
47544 KB |
Output is correct |
77 |
Correct |
1016 ms |
47544 KB |
Output is correct |
78 |
Correct |
824 ms |
47544 KB |
Output is correct |
79 |
Correct |
980 ms |
47544 KB |
Output is correct |
80 |
Correct |
911 ms |
47544 KB |
Output is correct |
81 |
Correct |
1382 ms |
47544 KB |
Output is correct |
82 |
Correct |
1399 ms |
47544 KB |
Output is correct |
83 |
Correct |
1493 ms |
47544 KB |
Output is correct |
84 |
Correct |
1251 ms |
47544 KB |
Output is correct |
85 |
Correct |
1296 ms |
47544 KB |
Output is correct |
86 |
Correct |
1267 ms |
47544 KB |
Output is correct |
87 |
Correct |
1282 ms |
47544 KB |
Output is correct |
88 |
Correct |
1883 ms |
47544 KB |
Output is correct |
89 |
Correct |
1890 ms |
47544 KB |
Output is correct |
90 |
Correct |
1874 ms |
47544 KB |
Output is correct |
91 |
Correct |
2154 ms |
47544 KB |
Output is correct |
92 |
Correct |
2148 ms |
47544 KB |
Output is correct |
93 |
Correct |
2253 ms |
47544 KB |
Output is correct |
94 |
Execution timed out |
3072 ms |
47544 KB |
Time limit exceeded |
95 |
Halted |
0 ms |
0 KB |
- |