#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int K = 3;
int N;
int X[303030];
int Y[303030];
int R[303030];
int XL[303030];
int XR[303030];
pii UL[303030][22];
pii UR[303030][22];
int V[303030][44];
int ulp[303030];
int urp[303030];
int vp[303030];
int ans[303030];
char rr;
struct DSU {
int n;
vector<int> l, r, c;
vector<bool> chk;
int cid;
void init(int _n) {
n = _n;
l.resize(n + 1); r.resize(n + 1);
c.resize(n); chk.resize(n);
cid = 0;
l[0] = -1; r[0] = n;
}
inline int left(int x) {
x = min(x, n - 1);
return x < 0 ? -1 : (chk[x] ? x : l[c[x]]);
}
inline int right(int x) {
x = max(x, 0);
return x >= n ? n : (chk[x] ? x : r[c[x]]);
}
void upd(int x) {
int lb = left(x), rb = right(x);
chk[x] = true;
cid++;
if (x - lb <= rb - x) {
for (int i = lb + 1; i < x; i++) c[i] = cid;
l[cid] = lb; r[cid] = x;
if (x < n - 1 && !chk[x + 1]) l[c[x + 1]] = x;
} else {
for (int i = x + 1; i < rb; i++) c[i] = cid;
l[cid] = x; r[cid] = rb;
if (x && !chk[x - 1]) r[c[x - 1]] = x;
}
}
};
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) {
int dx = X[i] - X[j], dy = Y[i] - Y[j], r = R[i] + R[j];
return (long long)dx * dx + (long long)dy * dy <= (long long)r * r;
}
inline void upd_ans(int cur, int cand) {
int &t = ans[cur];
if (R[t] > R[cand] || (R[t] == R[cand] && t < cand)) return;
if (intersect(cur, cand)) t = cand;
}
struct SegTree {
struct Node {
vector<pii> v;
DSU uf;
bool fg;
Node() : fg(false) {}
};
int n, base;
vector<Node> T;
SegTree(int _n) : n(_n) {
for (base = 1; base < n; base <<= 1);
T.resize(base + base);
}
void add_line(int p, int q, int y, int i) {
p += base; q += base;
p--; q--;
while (p <= q) {
if (p & 1) {
V[i][vp[i]++] = T[p].v.size();
T[p].v.emplace_back(y, i);
p++;
}
if (~q & 1) {
V[i][vp[i]++] = T[q].v.size();
T[q].v.emplace_back(y, i);
q--;
}
p >>= 1; q >>= 1;
}
}
void add_point(int p, int i, bool is_left) {
p += base; p--;
while (p) {
if (is_left) UL[i][ulp[i]++] = {p, (int)T[p].v.size()};
else UR[i][urp[i]++] = {p, (int)T[p].v.size()};
p >>= 1;
}
}
void upd(int p, int q, int i) {
p += base; q += base;
p--; q--;
int ptr = 0;
while (p <= q) {
if (p & 1) {
if (!T[p].fg) {
T[p].fg = true;
T[p].uf.init(T[p].v.size());
}
T[p].uf.upd(V[i][ptr++]);
p++;
}
if (~q & 1) {
if (!T[q].fg) {
T[q].fg = true;
T[q].uf.init(T[q].v.size());
}
T[q].uf.upd(V[i][ptr++]);
q--;
}
p >>= 1; q >>= 1;
}
}
void chk(int cur, bool is_left) {
if (is_left) {
for (int i = 0; i < ulp[cur]; i++) {
int p, s; tie(p, s) = UL[cur][i];
int t = s;
for (int j = 0; j < K; j++) {
t = T[p].uf.right(t);
if (t >= T[p].v.size()) break;
upd_ans(cur, T[p].v[t].second);
t++;
}
t = s;
for (int j = 0; j < K; j++) {
t = T[p].uf.left(t);
if (t < 0) break;
upd_ans(cur, T[p].v[t].second);
t--;
}
}
} else {
for (int i = 0; i < urp[cur]; i++) {
int p, s; tie(p, s) = UR[cur][i];
int t = s;
for (int j = 0; j < K; j++) {
t = T[p].uf.right(t);
if (t >= T[p].v.size()) break;
upd_ans(cur, T[p].v[t].second);
t++;
}
t = s;
for (int j = 0; j < K; j++) {
t = T[p].uf.left(t);
if (t < 0) break;
upd_ans(cur, T[p].v[t].second);
t--;
}
}
}
}
};
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);
vector<int> ord(N);
iota(ord.begin(), ord.end(), 1);
sort(ord.begin(), ord.end(), [&](int a, int b) { return Y[a] < Y[b]; });
for (int i : ord) {
seg.add_line(XL[i], XR[i], Y[i], i);
seg.add_point(XL[i], i, true);
seg.add_point(XR[i], i, false);
}
sort(ord.begin(), ord.end(), [&](int a, int b) {
if (R[a] == R[b]) return a < b;
return R[a] > R[b];
});
for (int i : ord) {
ans[i] = i;
seg.chk(i, true);
seg.chk(i, false);
if (ans[i] == i) seg.upd(XL[i], XR[i], i);
}
for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
return 0;
}
Compilation message
circle_selection.cpp: In member function 'void SegTree::chk(int, bool)':
circle_selection.cpp:158:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | if (t >= T[p].v.size()) break;
| ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:176:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | if (t >= T[p].v.size()) break;
| ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:232:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
232 | for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
| ^~~
circle_selection.cpp:232:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
232 | for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1505 ms |
567872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
571 ms |
192452 KB |
Output is correct |
| 3 |
Correct |
2011 ms |
630900 KB |
Output is correct |
| 4 |
Correct |
2017 ms |
629972 KB |
Output is correct |
| 5 |
Correct |
2306 ms |
620928 KB |
Output is correct |
| 6 |
Correct |
1026 ms |
315328 KB |
Output is correct |
| 7 |
Correct |
407 ms |
165828 KB |
Output is correct |
| 8 |
Correct |
41 ms |
45516 KB |
Output is correct |
| 9 |
Correct |
2091 ms |
632244 KB |
Output is correct |
| 10 |
Correct |
2693 ms |
616112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1609 ms |
624076 KB |
Output is correct |
| 2 |
Correct |
884 ms |
573616 KB |
Output is correct |
| 3 |
Incorrect |
2657 ms |
585528 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
