Submission #370740

#	Time	Username	Problem	Language	Result	Execution time	Memory
370740		luciocf	Circle selection (APIO18_circle_selection)	C++14	0 / 100	765 ms	75372 KiB

circle_selection

#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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13