#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
using namespace std;
const int inf = 1e9;
const int dydis = 3e5 + 1;
int n, m, v, ind;
int x, y, kur, R;
int dbInd = 0, mInd = 0;
vector<int> allX;
vector<int> l, r, ml, mr;
vector<pair<int, int> > treeVals;
vector<vector<pair<int, int> > > base;
vector<pair<pair<int, int>, pair<int, int> > > mas;
bitset<dydis> circleRemoved;
bitset<(4 * 21 * dydis)> removed;
vector<pair<int, int> > kurYra[dydis];
vector<int> rightmost;
vector<int> sz;
vector<int> tevas;
int by[dydis];
vector<int> unique(vector<int> &a) {
vector<int> ret;
sort(a.begin(), a.end());
for(auto &x : a){
if(ret.size() == 0 || ret.back() != x) ret.push_back(x);
}
return ret;
}
void build(int v) {
if(v >= m){
l[v] = r[v] = dbInd++;
ml[v] = mInd;
for(auto x : base[l[v]]) {
treeVals[mInd++] = x;
}
mr[v] = mInd-1;
}else {
build(v*2);
build(v*2+1);
l[v] = l[v*2];
r[v] = r[v*2+1];
ml[v] = mInd;
for(int i = ml[v*2]; i <= mr[v*2]; i++) {
treeVals[mInd++] = treeVals[i];
}
for(int i = ml[v*2+1]; i <= mr[v*2+1]; i++) {
treeVals[mInd++] = treeVals[i];
}
mr[v] = mInd-1;
if(ml[v] < mr[v]) sort(treeVals.begin() + ml[v], treeVals.begin() + mr[v] + 1);
}
for(int i = ml[v]; i <= mr[v]; i++) {
kurYra[treeVals[i].second].push_back({v, i});
}
}
int vec[dydis];
int id = 0, ret;
int fP(int v) {
id = 0;
while(true) {
vec[id++] = v;
ret = v;
if(tevas[v] == v) break;
v = tevas[v];
}
for(int i = 0; i < id; i++) tevas[vec[i]] = ret;
return ret;
}
void conn(int a, int b) {
a = fP(a);
b = fP(b);
if(sz[a] < sz[b]) swap(a, b);
tevas[b] = a;
sz[a] += sz[b];
rightmost[a] = max(rightmost[a], rightmost[b]);
}
void remove(int ind){
if(circleRemoved[ind]) return ;
circleRemoved[ind] = 1;
int i;
for(auto &x : kurYra[ind]) {
v = x.first;
i = x.second;
removed[i] = 1;
if(i-1 >= ml[v] && removed[i-1]) {
conn(i-1, i);
}
if(i+1 <= mr[v] && removed[i+1]) {
conn(i+1, i);
}
}
}
void print(int v) {
if(v < m){
print(v*2);
print(v*2+1);
}
cout << "v = " << v << ", [" << l[v] << "; " << r[v] << "], atitinkamas masyvas: [";
for(int i = ml[v]; i <= mr[v]; i++) {
if(removed[i]) continue;
cout << "(y=" << treeVals[i].first << ", i=" << treeVals[i].second << ")";
if(i != mr[v]) cout << ", ";
}
cout << "]\n";
}
long long X1, Y1, R1, X2, Y2, R2;
bool kertasi (int i, int j) {
X1 = mas[i].second.first; Y1 = mas[i].second.second; R1 = mas[i].first.first;
X2 = mas[j].second.first; Y2 = mas[j].second.second; R2 = mas[j].first.first;
return (X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2) <= (R1 + R2) * (R1 + R2);
}
int beg;
bitset<dydis> selected;
int selList[dydis];
int selInd = 0;
void find(int v, int L, int R, int down, int up){
if(L <= l[v] && r[v] <= R) {
beg = lower_bound(treeVals.begin() + ml[v], treeVals.begin() + mr[v] + 1, make_pair(down, -inf)) - treeVals.begin();
for(int i = beg; i <= mr[v]; i++) {
if(treeVals[i].first > up) break;
if(removed[i]) {
i = rightmost[fP(i)];
continue;
}
if(!selected[treeVals[i].second]) {
selected[treeVals[i].second] = 1;
selList[selInd++] = treeVals[i].second;
}
}
}else if(r[v] < L || R < l[v]) {
}else{
find(v*2, L, R, down, up);
find(v*2+1, L, R, down, up);
}
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
treeVals.resize(4 * 21 * dydis);
l.resize(2 * dydis);
r.resize(2 * dydis);
ml.resize(2 * dydis);
mr.resize(2 * dydis);
rightmost.resize(4 * 21 * dydis);
sz.resize(4 * 21 * dydis);
tevas.resize(4 * 21 * dydis);
for(int i = 0; i < (int) tevas.size(); i++) {
tevas[i] = i;
sz[i] = 1;
rightmost[i] = i;
}
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x >> y >> R;
mas.push_back({{R, -i}, {x, y}});
}
sort(mas.begin(), mas.end());
reverse(mas.begin(), mas.end());
for(auto &x : mas) x.first.second *= -1;
for(int i = 0; i < n; i++) {
allX.push_back(mas[i].second.first-mas[i].first.first);
allX.push_back(mas[i].second.first+mas[i].first.first);
}
allX = unique(allX);
base.resize(allX.size());
m = allX.size();
for(int i = 0; i < n; i++) {
x = mas[i].second.first;
y = mas[i].second.second;
R = mas[i].first.first;
kur = lower_bound(allX.begin(), allX.end(), x+R) - allX.begin();
base[kur].push_back({y-R, i});
base[kur].push_back({y+R, i});
kur = lower_bound(allX.begin(), allX.end(), x-R) - allX.begin();
base[kur].push_back({y-R, i});
base[kur].push_back({y+R, i});
}
for(auto &x : base) sort(x.begin(), x.end());
build(1);
//cout << "po buildo" << endl;
//cout << "mas:\n";
//for(int i = 0; i < n; i++) {
// auto &x = mas[i];
// cout <<i << ". " << "(" << x.second.first << ", " << x.second.second << "), r = " << x.first.first << endl;
//}
//cout << endl;
//cout << "x-ai:\n";
//for(int i = 0; i < m; i++) {
// cout << i << ". " << allX[i] << endl;
//}
//cout << endl;
//print(1);
//cout << endl;
int L, R, ll, rr;
for(int i = 0; i < n; i++) {
if(circleRemoved[i]) continue;
L = mas[i].second.first - mas[i].first.first;
R = mas[i].second.first + mas[i].first.first;
ll = lower_bound(allX.begin(), allX.end(), L) - allX.begin();
rr = lower_bound(allX.begin(), allX.end(), R) - allX.begin();
selInd = 0;
//cout << "Ieskau kvadratu, kurie kertasi su " << mas[i].first.second << "-uoju. ";
find(1, ll, rr, mas[i].second.second - mas[i].first.first, mas[i].second.second + mas[i].first.first);
//cout << "radau ";
for(int j = 0; j < selInd; j++){
selected[selList[j]] = 0;
if(!kertasi(i, selList[j])) continue;
//cout << mas[selList[j]].first.second << " ";
remove(selList[j]);
by[mas[selList[j]].first.second] = mas[i].first.second;
}
//cout << endl;
}
//cout << endl << endl << "ats: \n";
for(int i = 0; i < n; i++) {
cout << by[i] + 1 << " ";
}
return 0;
}
/*
5
0 0 3
5 -2 2
5 0 1
1 1 1
1 -3 1
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
265 ms |
509952 KB |
Output is correct |
2 |
Correct |
265 ms |
509824 KB |
Output is correct |
3 |
Correct |
260 ms |
510036 KB |
Output is correct |
4 |
Correct |
254 ms |
509940 KB |
Output is correct |
5 |
Correct |
259 ms |
509816 KB |
Output is correct |
6 |
Correct |
267 ms |
510016 KB |
Output is correct |
7 |
Correct |
250 ms |
509920 KB |
Output is correct |
8 |
Correct |
261 ms |
510060 KB |
Output is correct |
9 |
Correct |
262 ms |
509992 KB |
Output is correct |
10 |
Correct |
251 ms |
509924 KB |
Output is correct |
11 |
Correct |
251 ms |
509996 KB |
Output is correct |
12 |
Correct |
275 ms |
509916 KB |
Output is correct |
13 |
Correct |
256 ms |
509896 KB |
Output is correct |
14 |
Correct |
263 ms |
509988 KB |
Output is correct |
15 |
Correct |
239 ms |
509980 KB |
Output is correct |
16 |
Correct |
262 ms |
510700 KB |
Output is correct |
17 |
Correct |
265 ms |
510652 KB |
Output is correct |
18 |
Correct |
268 ms |
510624 KB |
Output is correct |
19 |
Correct |
292 ms |
513568 KB |
Output is correct |
20 |
Correct |
265 ms |
513716 KB |
Output is correct |
21 |
Correct |
279 ms |
513660 KB |
Output is correct |
22 |
Correct |
281 ms |
513440 KB |
Output is correct |
23 |
Correct |
286 ms |
513432 KB |
Output is correct |
24 |
Correct |
287 ms |
513408 KB |
Output is correct |
25 |
Correct |
308 ms |
513436 KB |
Output is correct |
26 |
Correct |
283 ms |
513440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3076 ms |
878820 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
259 ms |
509924 KB |
Output is correct |
2 |
Correct |
1673 ms |
630988 KB |
Output is correct |
3 |
Execution timed out |
3067 ms |
864288 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3087 ms |
858196 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
329 ms |
517272 KB |
Output is correct |
2 |
Correct |
318 ms |
517284 KB |
Output is correct |
3 |
Correct |
314 ms |
517272 KB |
Output is correct |
4 |
Correct |
338 ms |
516868 KB |
Output is correct |
5 |
Correct |
305 ms |
516976 KB |
Output is correct |
6 |
Correct |
301 ms |
516812 KB |
Output is correct |
7 |
Correct |
1305 ms |
636900 KB |
Output is correct |
8 |
Correct |
1350 ms |
636808 KB |
Output is correct |
9 |
Correct |
1459 ms |
635868 KB |
Output is correct |
10 |
Correct |
1495 ms |
630584 KB |
Output is correct |
11 |
Correct |
1379 ms |
630808 KB |
Output is correct |
12 |
Correct |
1429 ms |
630736 KB |
Output is correct |
13 |
Correct |
1092 ms |
571444 KB |
Output is correct |
14 |
Correct |
1066 ms |
571408 KB |
Output is correct |
15 |
Correct |
1091 ms |
571396 KB |
Output is correct |
16 |
Correct |
1256 ms |
571572 KB |
Output is correct |
17 |
Correct |
1166 ms |
630432 KB |
Output is correct |
18 |
Correct |
1207 ms |
630316 KB |
Output is correct |
19 |
Correct |
1185 ms |
630320 KB |
Output is correct |
20 |
Correct |
1228 ms |
630376 KB |
Output is correct |
21 |
Correct |
1162 ms |
630320 KB |
Output is correct |
22 |
Correct |
1213 ms |
630608 KB |
Output is correct |
23 |
Correct |
1195 ms |
630296 KB |
Output is correct |
24 |
Correct |
1249 ms |
630304 KB |
Output is correct |
25 |
Correct |
265 ms |
509952 KB |
Output is correct |
26 |
Correct |
265 ms |
509824 KB |
Output is correct |
27 |
Correct |
260 ms |
510036 KB |
Output is correct |
28 |
Correct |
254 ms |
509940 KB |
Output is correct |
29 |
Correct |
259 ms |
509816 KB |
Output is correct |
30 |
Correct |
267 ms |
510016 KB |
Output is correct |
31 |
Correct |
250 ms |
509920 KB |
Output is correct |
32 |
Correct |
261 ms |
510060 KB |
Output is correct |
33 |
Correct |
262 ms |
509992 KB |
Output is correct |
34 |
Correct |
251 ms |
509924 KB |
Output is correct |
35 |
Correct |
251 ms |
509996 KB |
Output is correct |
36 |
Correct |
275 ms |
509916 KB |
Output is correct |
37 |
Correct |
256 ms |
509896 KB |
Output is correct |
38 |
Correct |
263 ms |
509988 KB |
Output is correct |
39 |
Correct |
239 ms |
509980 KB |
Output is correct |
40 |
Correct |
262 ms |
510700 KB |
Output is correct |
41 |
Correct |
265 ms |
510652 KB |
Output is correct |
42 |
Correct |
268 ms |
510624 KB |
Output is correct |
43 |
Correct |
292 ms |
513568 KB |
Output is correct |
44 |
Correct |
265 ms |
513716 KB |
Output is correct |
45 |
Correct |
279 ms |
513660 KB |
Output is correct |
46 |
Correct |
281 ms |
513440 KB |
Output is correct |
47 |
Correct |
286 ms |
513432 KB |
Output is correct |
48 |
Correct |
287 ms |
513408 KB |
Output is correct |
49 |
Correct |
308 ms |
513436 KB |
Output is correct |
50 |
Correct |
283 ms |
513440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3134 ms |
879860 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |