#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 300005;
constexpr int MAXINT = 1073741823;
vector<int> all_numbers;
struct circles {
int x, y, radius;
} circle[MAXN];
int sorted[MAXN], answer[MAXN];
bitset<MAXN> deleted;
set<int> segment[MAXN * 8];
bool comparison(int x, int y) {
return (circle[x].radius == circle[y].radius? x < y : circle[x].radius > circle[y].radius);
}
void add(int from, int to, int current, int index, int value) {
if (from > index || to < index)
return;
segment[current].insert(value);
if (from == to)
return;
int mid = (from + to) / 2;
add(from, mid, current * 2 + 1, index, value);
add(mid + 1, to, current * 2 + 2, index, value);
return;
}
void eliminate(int from, int to, int current, int index, int value) {
if (from > index || to < index)
return;
segment[current].erase(value);
if (from == to)
return;
int mid = (from + to) / 2;
add(from, mid, current * 2 + 1, index, value);
add(mid + 1, to, current * 2 + 2, index, value);
return;
}
vector<int> selection, to_delete;
void select(int from, int to, int current, int beginning, int ending) {
if (from > ending || to < beginning)
return;
else if (beginning <= from && to <= ending) {
selection.push_back(current);
return;
}
int mid = (from + to) / 2;
select(from, mid, current * 2 + 1, beginning, ending);
select(mid + 1, to, current * 2 + 2, beginning, ending);
return;
}
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;
all_numbers.push_back(circle[i].x - circle[i].radius);
all_numbers.push_back(circle[i].x + circle[i].radius);
sorted[i] = i;
}
sort(sorted, sorted + n, comparison);
sort(all_numbers.begin(), all_numbers.end());
all_numbers.resize(distance(all_numbers.begin(), unique(all_numbers.begin(), all_numbers.end())));
for (int i = 0; i < n; i++) {
circle[i].y = lower_bound(all_numbers.begin(), all_numbers.end(), circle[i].x + circle[i].radius) - all_numbers.begin();
circle[i].x = lower_bound(all_numbers.begin(), all_numbers.end(), circle[i].x - circle[i].radius) - all_numbers.begin();
add(0, all_numbers.size() - 1, 0, circle[i].x, i);
add(0, all_numbers.size() - 1, 0, circle[i].y, i);
}
for (int i = 0; i < n; i++)
if (!deleted[sorted[i]]) {
deleted[sorted[i]] = true;
selection.clear();
select(0, all_numbers.size() - 1, 0, circle[sorted[i]].x, circle[sorted[i]].y);
to_delete.clear();
for (int j : selection)
to_delete.insert(to_delete.end(), segment[j].begin(), segment[j].end());
for (int j : to_delete) {
answer[j] = sorted[i];
deleted[j] = true;
eliminate(0, all_numbers.size() - 1, 0, circle[j].x, j);
eliminate(0, all_numbers.size() - 1, 0, circle[j].y, j);
}
}
for (int i = 0; i < n; i++)
cout << answer[i] + 1 << ' ';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
112964 KB |
Output is correct |
| 2 |
Correct |
61 ms |
113040 KB |
Output is correct |
| 3 |
Incorrect |
68 ms |
113096 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
309360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
113040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
324224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
112964 KB |
Output is correct |
| 2 |
Correct |
61 ms |
113040 KB |
Output is correct |
| 3 |
Incorrect |
68 ms |
113096 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
112964 KB |
Output is correct |
| 2 |
Correct |
61 ms |
113040 KB |
Output is correct |
| 3 |
Incorrect |
68 ms |
113096 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
