#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
const int maxn = 3e5+10;
const ll inf = 1e18+10;
int n;
struct Circle
{
int x, y, r, ind;
} circle[maxn];
struct Node
{
pii v;
int w, sz;
ll val, mx_val;
int id;
Node *l, *r;
Node(pii vv, ll vval, int idd)
{
v = vv, val = mx_val = vval, id = idd, sz = 1, w = rand();
l = r = NULL;
}
};
typedef Node*& node_t;
struct Treap
{
Node *root;
int sz(Node *t)
{
return (t ? t->sz : 0);
}
ll get_val(Node *t)
{
return (t ? t->mx_val : -inf);
}
int get_id(Node *t)
{
return (t ? t->id : 0);
}
void op(Node *t)
{
if (t)
{
t->sz = sz(t->l) + sz(t->r) + 1;
if (max({get_val(t->l), get_val(t->r), t->val}) == get_val(t->l))
{
t->mx_val = get_val(t->l);
t->id = get_id(t->l);
}
else if (max({get_val(t->l), get_val(t->r), t->val}) == get_val(t->r))
{
t->mx_val = get_val(t->r);
t->id = get_id(t->r);
}
else
{
t->mx_val = t->val;
t->id = t->v.ss;
}
}
}
void split(Node *t, node_t l, node_t r, pii v)
{
if (!t) return void(l = r = NULL);
if (t->v > v) split(t->l, l, t->l, v), r = t;
else split(t->r, t->r, r, v), l = t;
op(t);
}
void merge(node_t t, Node *l, Node *r)
{
if (!l || !r) t = (l ? l : r);
else if (l->w > r->w) merge(l->r, l->r, r), t = l;
else merge(r->l, l, r->l), t = r;
op(t);
}
void insert(node_t t, Node *aux)
{
if (!t) t = aux;
else if (aux->w > t->w) split(t, aux->l, aux->r, aux->v), t = aux;
else insert((aux->v > t->v ? t->r : t->l), aux);
op(t);
}
void erase(node_t t, pii v)
{
if (t->v == v) merge(t, t->l, t->r);
else erase((v > t->v ? t->r : t->l), v);
op(t);
}
pii query(Node *t, int l, int r)
{
Node *t1 = NULL, *t2 = NULL, *t3 = NULL;
split(t, t1, t2, {l-1, 1e9});
split(t2, t2, t3, {r, 1e9});
pii ans = {get_val(t2), get_id(t2)};
merge(t2, t2, t3);
merge(t, t1, t2);
return ans;
}
};
struct SegmentTree
{
Treap tree[2][maxn];
void upd(int node, int q, int l, int r, int pos_x, int pos_y, ll v, int ind)
{
Node *aux = new Node({pos_y, ind}, v, ind);
tree[q][node].insert(tree[q][node].root, aux);
if (l == r) return;
int mid = (l+r)>>1;
if (pos_x <= mid) upd(2*node, q, l, mid, pos_x, pos_y, v, ind);
else upd(2*node+1, q, mid+1, r, pos_x, pos_y, v, ind);
}
void erase(int node, int q, int l, int r, int pos_x, int pos_y, int ind)
{
tree[q][node].erase(tree[q][node].root, {pos_y, ind});
if (l == r) return;
int mid = (l+r)>>1;
if (pos_x <= mid) erase(2*node, q, l, mid, pos_x, pos_y, ind);
else erase(2*node+1, q, mid+1, r, pos_x, pos_y, ind);
}
pii query(int node, int q, int l, int r, int a_x, int b_x, int a_y, int b_y)
{
if (l > b_x || r < a_x) return {-inf, 0};
if (l >= a_x && r <= b_x) return tree[q][node].query(tree[q][node].root, a_y, b_y);
int mid = (l+r)>>1;
return max(query(2*node, q, l, mid, a_x, b_x, a_y, b_y), query(2*node+1, q, mid+1, r, a_x, b_x, a_y, b_y));
}
} seg[2];
int ans[maxn];
map<int, int> mp_x, mp_y;
bool comp(Circle a, Circle b)
{
if (a.r == b.r) return a.ind < b.ind;
return a.r > b.r;
}
void rem(int i)
{
int x = mp_x[circle[i].x], y = mp_y[circle[i].y];
seg[0].erase(1, 0, 1, n, x, y, i);
seg[0].erase(1, 1, 1, n, x, y, i);
seg[1].erase(1, 0, 1, n, x, y, i);
seg[1].erase(1, 1, 1, n, x, y, i);
}
int main(void)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d %d %d", &circle[i].x, &circle[i].y, &circle[i].r);
circle[i].ind = i;
mp_x[circle[i].x] = 0;
mp_y[circle[i].y] = 0;
}
sort(circle+1, circle+n+1, comp);
int aux = 0;
for (auto &x: mp_x)
x.second = ++aux;
aux = 0;
for (auto &x: mp_y)
x.second = ++aux;
for (int i = 1; i <= n; i++)
{
int x = mp_x[circle[i].x], y = mp_y[circle[i].y];
ll v = 1ll*circle[i].x + 1ll*circle[i].y + 1ll*circle[i].r;
seg[0].upd(1, 0, 1, n, x, y, v, i);
v = 1ll*circle[i].x - 1ll*circle[i].y + 1ll*circle[i].r;
seg[0].upd(1, 1, 1, n, x, y, v, i);
v = -1ll*circle[i].x + 1ll*circle[i].y + 1ll*circle[i].r;
seg[1].upd(1, 0, 1, n, x, y, v, i);
v = -1ll*circle[i].x - 1ll*circle[i].y + 1ll*circle[i].r;
seg[1].upd(1, 1, 1, n, x, y, v, i);
}
for (int i = 1; i <= n; i++)
{
if (ans[circle[i].ind]) continue;
ans[circle[i].ind] = circle[i].ind;
rem(i);
int x = mp_x[circle[i].x], y = mp_y[circle[i].y];
while (true)
{
ll v = 1ll*circle[i].x + 1ll*circle[i].y - 1ll*circle[i].r;
pii P = seg[0].query(1, 0, 1, n, 1, x, 1, y);
if (P.ff >= v)
{
ans[circle[P.ss].ind] = circle[i].ind;
rem(P.ss);
continue;
}
v = 1ll*circle[i].x - 1ll*circle[i].y - 1ll*circle[i].r;
P = seg[0].query(1, 1, 1, n, 1, x, y, n);
if (P.ff >= v)
{
ans[circle[P.ss].ind] = circle[i].ind;
rem(P.ss);
continue;
}
v = -1ll*circle[i].x + 1ll*circle[i].y - 1ll*circle[i].r;
P = seg[1].query(1, 0, 1, n, x, n, 1, y);
if (P.ff >= v)
{
ans[circle[P.ss].ind] = circle[i].ind;
rem(P.ss);
continue;
}
v = -1ll*circle[i].x - 1ll*circle[i].y - 1ll*circle[i].r;
P = seg[1].query(1, 1, 1, n, x, n, y, n);
if (P.ff >= v)
{
ans[circle[P.ss].ind] = circle[i].ind;
rem(P.ss);
continue;
}
break;
}
}
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
printf("\n");
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:194:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
194 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
circle_selection.cpp:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
198 | scanf("%d %d %d", &circle[i].x, &circle[i].y, &circle[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
427 ms |
46024 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
765 ms |
75372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
