#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100, CHK = 2;
struct Circle{
int x, y, r, i, xl, xr;
Circle(){}
bool operator < (const Circle &C) const{
if (r==C.r) return i < C.i;
return r > C.r;
}
}C[300300];
int ans[300300];
int ok(int i, int j){
ll d = (ll)(C[i].x-C[j].x) * (C[i].x-C[j].x) + (ll)(C[i].y-C[j].y) * (C[i].y-C[j].y);
ll r = (ll)(C[i].r + C[j].r) * (C[i].r + C[j].r);
return d <= r;
}
struct Seg{
int sz;
map<int, int> tree[1201200];
map<int, int>::iterator iter0[30], iter[30];
int T[30], buf[30], pt, py = INF;
void init(int n){
sz = n;
}
void update(int l, int r, int y, int i){
r++;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1){
tree[l][y] = i;
l++;
}
if (r&1){
--r;
tree[r][y] = i;
}
}
}
int queryU(int x, int y, int i){
pt = 0;
for (int node=x+sz;node>0;node>>=1){
if (y!=py || T[pt] != node) iter0[pt] = tree[node].lower_bound(y);
iter[pt] = iter0[pt];
T[pt] = node;
buf[pt] = (iter[pt]==tree[T[pt]].end())?INF:iter[pt]->first;
pt++;
}
py = y;
int ret = i;
for (int _=0;_<CHK;_++){
int idx = min_element(buf, buf+pt) - buf;
if (buf[idx]==INF) break;
if (ok(i, iter[idx]->second)) ret = min(ret, iter[idx]->second);
iter[idx]++;
buf[idx] = (iter[idx]==tree[T[idx]].end())?INF:iter[idx]->first;
}
return ret;
}
int queryD(int i){
for (int i=0;i<pt;i++){
iter[i] = iter0[i];
buf[i] = (iter[i]==tree[T[i]].begin())?(-INF):prev(iter[i])->first;
}
int ret = i;
for (int _=0;_<CHK;_++){
int idx = max_element(buf, buf+pt) - buf;
if (buf[idx]==-INF) break;
iter[idx]--;
if (ok(i, iter[idx]->second)) ret = min(ret, iter[idx]->second);
buf[idx] = (iter[idx]==tree[T[idx]].begin())?(-INF):prev(iter[idx])->first;
}
return ret;
}
}tree;
int calc(int x, int i){
int ret = i;
ret = min(ret, tree.queryU(x, C[i].y, i));
ret = min(ret, tree.queryD(i));
return ret;
}
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
static unsigned char str[40002000], *p=str;
int main(){
fread(str, 1, 12002000, stdin);
int n;
rf(n);
vector<int> X;
for (int i=1;i<=n;i++){
rf(C[i].x);
rf(C[i].y);
rf(C[i].r);
X.push_back(C[i].x - C[i].r);
X.push_back(C[i].x + C[i].r);
C[i].i = i;
}
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
for (int i=1;i<=n;i++){
C[i].xl = lower_bound(X.begin(), X.end(), C[i].x - C[i].r) - X.begin();
C[i].xr = lower_bound(X.begin(), X.end(), C[i].x + C[i].r) - X.begin();
}
sort(C+1, C+n+1);
tree.init(X.size());
for (int i=1;i<=n;i++){
ans[C[i].i] = min(calc(C[i].xl, i), calc(C[i].xr, i));
if (ans[C[i].i]==i) tree.update(C[i].xl, C[i].xr, C[i].y, i);
ans[C[i].i] = C[ans[C[i].i]].i;
}
for (int i=1;i<=n;i++) printf("%d ", ans[i]);
printf("\n");
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:112:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | fread(str, 1, 12002000, stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
59996 KB |
Output is correct |
2 |
Correct |
12 ms |
59996 KB |
Output is correct |
3 |
Correct |
12 ms |
60088 KB |
Output is correct |
4 |
Correct |
12 ms |
60056 KB |
Output is correct |
5 |
Correct |
13 ms |
60372 KB |
Output is correct |
6 |
Correct |
12 ms |
59996 KB |
Output is correct |
7 |
Correct |
12 ms |
59996 KB |
Output is correct |
8 |
Incorrect |
12 ms |
59996 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
376 ms |
78008 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
59992 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1056 ms |
148104 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
59996 KB |
Output is correct |
2 |
Correct |
12 ms |
59996 KB |
Output is correct |
3 |
Correct |
12 ms |
60088 KB |
Output is correct |
4 |
Correct |
12 ms |
60056 KB |
Output is correct |
5 |
Correct |
13 ms |
60372 KB |
Output is correct |
6 |
Correct |
12 ms |
59996 KB |
Output is correct |
7 |
Correct |
12 ms |
59996 KB |
Output is correct |
8 |
Incorrect |
12 ms |
59996 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
59996 KB |
Output is correct |
2 |
Correct |
12 ms |
59996 KB |
Output is correct |
3 |
Correct |
12 ms |
60088 KB |
Output is correct |
4 |
Correct |
12 ms |
60056 KB |
Output is correct |
5 |
Correct |
13 ms |
60372 KB |
Output is correct |
6 |
Correct |
12 ms |
59996 KB |
Output is correct |
7 |
Correct |
12 ms |
59996 KB |
Output is correct |
8 |
Incorrect |
12 ms |
59996 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |