#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e18, N = 3e5 + 5;
vector<int> seg(N * 4, INF);
int parl[N], parr[N];
bool cmp(array<int, 3> a, array<int, 3> b)
{
if(a[0] != b[0])
{
return a[0] > b[0];
}
return a[1] < b[1];
}
void Update(int l, int r, int pos, int ql, int qr, int qval)
{
if(ql <= l && r <= qr)
{
seg[pos] = qval;
return;
}
if(ql > r || l > qr)
{
return;
}
int mid = (l + r) / 2;
Update(l, mid, pos * 2, ql, qr, qval);
Update(mid + 1, r, pos * 2 + 1, ql, qr, qval);
}
int Query(int l, int r, int pos, int qpos)
{
if(seg[pos] != INF)
{
return seg[pos];
}
int mid = (l + r) >> 1;
if(qpos <= mid)
{
return Query(l, mid, pos * 2, qpos);
}
return Query(mid + 1, r, pos * 2 + 1, qpos);
}
int FindL(int x)
{
if(x == parl[x])
{
return x;
}
return parl[x] = FindL(parl[x]);
}
void UniteL(int u, int v)
{
u = FindL(u);
v = FindL(v);
if(u == v) return;
parl[max(u, v)] = min(u, v);
}
int FindR(int x)
{
if(x == parr[x])
{
return x;
}
return parr[x] = FindR(parr[x]);
}
void UniteR(int u, int v)
{
u = FindR(u);
v = FindR(v);
if(u == v) return;
parr[min(u, v)] = max(u, v);
}
void Solve()
{
int n;
cin >> n;
vector<array<int, 3> > circle(n + 1);
map<int, int> mp, revmp;
for(int i = 1; i <= n; i++)
{
parl[i] = i;
parr[i] = i;
cin >> circle[i][0] >> circle[i][1] >> circle[i][2];
mp[circle[i][0]]++;
}
int cnt = 0;
for(auto i: mp)
{
mp[i.first] = ++cnt;
revmp[cnt] = i.first;
}
for(int i = 1; i <= n; i++)
{
circle[i][0] = mp[circle[i][0]];
}
vector<array<int, 3> > order;
for(int i = 1; i <= n; i++)
{
order.push_back({circle[i][2], i, circle[i][0]});
}
sort(order.begin(), order.end(), cmp);
reverse(order.begin(), order.end());
for(auto [radius, idx, x]: order)
{
Update(1, n, 1, x, x, idx);
}
// cout << "cnt = " << cnt << endl;
// for(int i = 1; i <= cnt; i++)
// {
// cout << revmp[i] << " ";
// }
// cout << endl;
reverse(order.begin(), order.end());
for(auto [radius, idx, x]: order)
{
// cout << "order(" << radius << ", " << idx << ", " << x << ")" << endl;
// cout << "Query(" << x << ") = " << Query(1, n, 1, x) << endl;
if(Query(1, n, 1, x) != idx)
{
continue;
}
int left = x, right = x;
int l = 1, r = x;
while(l <= r)
{
int mid = (l + r) >> 1;
if(revmp[mid] >= revmp[x] - radius)
{
r = mid - 1;
left = mid;
}
else
{
l = mid + 1;
}
}
l = x;
r = cnt;
while(l <= r)
{
int mid = (l + r) >> 1;
if(revmp[mid] <= revmp[x] + radius)
{
l = mid + 1;
right = mid;
}
else
{
r = mid - 1;
}
}
left = FindR(left);
right = FindL(right);
// cout << "left = " << left << ", right = " << right << endl;
Update(1, n, 1, left, right, idx);
for(int i = left; i <= right; i++)
{
UniteL(i, i - 1);
UniteR(i, i + 1);
}
}
for(int i = 1; i <= n; i++)
{
cout << Query(1, n, 1, circle[i][0]) << " ";
}
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
//cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
/*
Sample 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
*/
Compilation message
circle_selection.cpp: In function 'void Solve()':
circle_selection.cpp:115:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | for(auto [radius, idx, x]: order)
| ^
circle_selection.cpp:126:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
126 | for(auto [radius, idx, x]: order)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
650 ms |
71460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1826 ms |
71416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
