#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int N;
int X[303030];
int Y[303030];
int R[303030];
int XL[303030];
int XR[303030];
int ans[303030];
int cur;
char rr;
void rf(int &x) {
x = 0;
int sgn = 0;
while (rr < 48 && rr != '-') rr = getchar();
if (rr == '-') { sgn = 1; rr = getchar(); }
while (47 < rr) { x = (x << 3) + (x << 1) + (rr & 15); rr = getchar(); }
if (sgn) x = -x;
}
inline bool intersect(int i, int j) {
long long dx = X[i] - X[j], dy = Y[i] - Y[j], r = R[i] + R[j];
return dx * dx + dy * dy <= r * r;
}
inline bool chk(int cand) {
if (intersect(cur, cand)) { ans[cand] = cur; return true; }
return false;
}
struct SegTree {
struct Node {
set<pii> s;
};
int n, base;
vector<Node> T;
SegTree(int _n) : n(_n) {
for (base = 1; base < n; base <<= 1);
T.resize(base + base);
}
void chk_node(int idx, int y) {
auto it = T[idx].s.lower_bound({y, 0});
auto tmp = it;
int cnt = 0;
while (it != T[idx].s.begin()) {
it--;
if (ans[it->second] || ::chk(it->second)) { it = T[idx].s.erase(it); continue; }
cnt++;
if (cnt >= 2) break;
}
cnt = 0;
it = tmp;
while (it != T[idx].s.end()) {
if (ans[it->second] || ::chk(it->second)) { it = T[idx].s.erase(it); continue; }
cnt++;
if (cnt >= 2) break;
it++;
}
}
void upd(int p, pii x) {
p += base; p--;
while (p) {
T[p].s.insert(x);
p >>= 1;
}
}
void chk(int p, int q, int y) {
p += base; q += base;
p--; q--;
while (p <= q) {
if (p & 1) chk_node(p++, y);
if (~q & 1) chk_node(q--, y);
p >>= 1; q >>= 1;
}
}
};
int main() {
rf(N);
vector<int> v;
for (int i = 1; i <= N; i++) {
rf(X[i]); rf(Y[i]); rf(R[i]);
XL[i] = X[i] - R[i], XR[i] = X[i] + R[i];
v.push_back(XL[i]);
v.push_back(XR[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= N; i++) {
XL[i] = lower_bound(v.begin(), v.end(), XL[i]) - v.begin() + 1;
XR[i] = lower_bound(v.begin(), v.end(), XR[i]) - v.begin() + 1;
}
int M = v.size();
SegTree seg(M);
for (int i = 1; i <= N; i++) {
seg.upd(XL[i], {Y[i], i});
seg.upd(XR[i], {Y[i], i});
}
vector<int> idx(N);
iota(idx.begin(), idx.end(), 1);
sort(idx.begin(), idx.end(), [&](int a, int b) {
return pii(R[a], -a) > pii(R[b], -b);
});
for (int i : idx) {
if (ans[i]) continue;
cur = ans[i] = i;
seg.chk(XL[i], XR[i], Y[i]);
}
for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
return 0;
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:124:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
124 | for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
| ^~~
circle_selection.cpp:124:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
124 | for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6504 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6492 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6488 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Incorrect |
4 ms |
7772 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3063 ms |
400500 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1815 ms |
153360 KB |
Output is correct |
3 |
Execution timed out |
3046 ms |
353144 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3029 ms |
357396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6504 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6492 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6488 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Incorrect |
4 ms |
7772 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6504 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6492 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6488 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Incorrect |
4 ms |
7772 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |