#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 300005;
constexpr int MAXINT = 1073741823;
struct circles {
int x, y, radius;
} circle[MAXN];
int sorted[MAXN], answer[MAXN];
bitset<MAXN> deleted;
set<pair<int, int>> lefts;
set<pair<int, int>> rights;
set<pair<int, int>>::iterator it;
bool comparison(int x, int y) {
return (circle[x].radius == circle[y].radius? x < y : circle[x].radius > circle[y].radius);
}
vector<int> to_delete;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> circle[i].x >> circle[i].y >> circle[i].radius;
lefts.emplace(circle[i].x - circle[i].radius, i);
rights.emplace(circle[i].x + circle[i].radius, i);
sorted[i] = i;
}
sort(sorted, sorted + n, comparison);
for (int i = 0; i < n; i++)
if (!deleted[sorted[i]]) {
to_delete.clear();
it = lefts.lower_bound(make_pair(circle[sorted[i]].x - circle[sorted[i]].radius, 0));
while (it != lefts.end() && it->first <= circle[sorted[i]].x + circle[sorted[i]].radius) {
to_delete.push_back(it->second);
it++;
}
it = rights.lower_bound(make_pair(circle[sorted[i]].x - circle[sorted[i]].radius, 0));
while (it != rights.end() && it->first <= circle[sorted[i]].x + circle[sorted[i]].radius) {
to_delete.push_back(it->second);
it++;
}
for (int j : to_delete) {
lefts.erase(make_pair(circle[j].x - circle[j].radius, j));
rights.erase(make_pair(circle[j].x - circle[j].radius, j));
answer[j] = sorted[i];
deleted[j] = true;
}
}
for (int i = 0; i < n; i++)
cout << answer[i] + 1 << ' ';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
944 ms |
38292 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
721 ms |
36044 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |