| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 260441 | Kastanda | Circle selection (APIO18_circle_selection) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005, INF = 1e9 + 9;
int n, X[N], Y[N], R[N], M[N];
vector < int > UX;
vector < pair < int , int > > V[N * 2];
set < pair < int , int > > ST[N * 2];
inline int GetId(int a)
{
return (int)(lower_bound(UX.begin(), UX.end(), a) - UX.begin());
}
inline bool Check(int i, int j)
{
return ((ll)(X[i] - X[j]) * (ll)(X[i] - X[j]) + (ll)(Y[i] - Y[j]) * (ll)(Y[i] - Y[j]) <= (ll)(R[i] + R[j]) * (ll)(R[i] + R[j]));
}
inline void Get(int l, int r, int le, int ri, int i)
{
l += (int)UX.size();
r += (int)UX.size();
for (; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
{
auto it = ST[l].lower_bound({le, -1});
while (it != ST[l].end() && it->first < ri)
{
if (M[it->second])
it = ST[l].erase(it);
else if (Check(i, it->second))
M[it->second] = i, it = ST[l].erase(it);
else
it ++;
}
l ++;
}
if (r & 1)
{
r --;
auto it = ST[r].lower_bound({le, -1});
while (it != ST[r].end() && it->first < ri)
{
if (M[it->second])
it = ST[r].erase(it);
else if (Check(i, it->second))
M[it->second] = i, it = ST[r].erase(it);
else
it ++;
}
}
}
}
inline void Do(int i)
{
M[i] = i;
int lx = GetId(max(X[i] - R[i] * 2LL, -INF));
int rx = GetId(min(X[i] + R[i] * 2LL + 1, INF));
int ly = max(Y[i] - R[i] * 2LL, (ll)-INF);
int ry = min(Y[i] + R[i] * 2LL + 1, (ll)INF);
Get(lx, rx, ly, ry, i);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d%d%d", &X[i], &Y[i], &R[i]), UX.push_back(X[i]);
sort(UX.begin(), UX.end());
UX.resize(unique(UX.begin(), UX.end()) - UX.begin());
for (int i = 1; i <= n; i ++)
{
int x = GetId(X[i]);
V[x + (int)UX.size()].push_back({Y[i], i});
}
for (int i = (int)UX.size(); i < (int)UX.size() * 2; i ++)
sort(V[i].begin(), V[i].end());
for (int i = (int)UX.size() - 1; i; i --)
merge(V[i << 1].begin(), V[i << 1].end(), V[i << 1 ^ 1].begin(), V[i << 1 ^ 1].end(), back_inserter(V[i]));
for (int i = 0; i < (int)UX.size() * 2; i ++)
ST[i] = set < pair < int , int > > (V[i].begin(), V[i].end());
set < pair < int , int > > TS;
for (int i = 1; i <= n; i ++)
TS.insert({-R[i], i});
while (TS.size())
{
while (TS.size() && M[TS.begin()->second])
TS.erase(TS.begin());
if (!TS.size())
break;
int i = TS.begin()->second;
TS.erase(TS.begin());
Do(i);
}
for (int i = 1; i <= n; i ++)
printf("%d ", M[i]);
printf("\n");
return 0;
}