Submission #370740

#TimeUsernameProblemLanguageResultExecution timeMemory
370740luciocfCircle selection (APIO18_circle_selection)C++14
0 / 100
765 ms75372 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...