Submission #102831

#	Time	Username	Problem	Language	Result	Execution time	Memory
102831		luciocf	Jousting tournament (IOI12_tournament)	C++14	0 / 100	40 ms	8056 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

struct node
{
	node *l, *r;
	int v, res, sz, w, maiorV, maiorRes, lazy;

	node(int vv, int rr)
	{
		v = maiorV = vv, res = maiorRes = rr;
		sz = 1, w = rand();
		l = r = NULL;
	}
};

typedef node*& node_t;

int sz(node *t) {return (t ? t->sz : 0);}

int maiorV(node *t) {return (t ? t->maiorV : -1);}

int maiorRes(node *t) {return (t ? t->maiorRes : -1);}

void op(node *t)
{
	if (t)
	{
		t->sz = sz(t->l)+sz(t->r)+1;
		t->maiorV = max({maiorV(t->l), maiorV(t->r), t->v});
		t->maiorRes = max({maiorRes(t->l), maiorRes(t->r), t->res}); 
	}
}

void split(node *t, node_t l, node_t r, int pos, int add=0)
{
	if (!t) return void(l=r=NULL);

	int v = add+sz(t->l);

	if (v >= pos) split(t->l, l, t->l, pos, add), r = t;
	else split(t->r, t->r, r, pos, v+1), 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, int pos, int v, int r)
{
	node *t1 = NULL, *t2 = NULL;
	node *aux = new node(v, r);

	split(t, t1, t2, pos);
	merge(t1, t1, aux);
	merge(t, t1, t2);

	op(t);
}

void erase(node_t t, int l, int r)
{
	node *t1 = NULL, *t2 = NULL, *t3 = NULL;

	split(t, t1, t2, l);
	split(t2, t2, t3, r-l+1);
	merge(t, t1, t3);

	op(t);
}

int query(node *t, int l, int r, bool tipo)
{
	node *t1 = NULL, *t2 = NULL, *t3 = NULL;

	split(t, t1, t2, l);
	split(t2, t2, t3, r-l+1);

	int ans = (tipo == 0 ? t2->maiorV : t2->maiorRes);

	merge(t2, t2, t3);
	merge(t, t1, t2);

	return ans;
}

int findV(node *t, int l, int r, int v, int add=0)
{
	int ind = add+sz(t->l);
	if (ind < l) return findV(t->r, l, r, v, ind+1);
	if (ind > r) return findV(t->l, l, r, v, add);

	if (t->v == v) return t->res;
	else if (maiorV(t->l) == v && add+sz(t->l->l) >= l) return findV(t->l, l, r, v, add);
	return findV(t->r, l, r, v, add);
}

int findRes(node *t, int l, int r, int res, int add=0)
{
	int ind = add+sz(t->l);
	if (ind < l) return findRes(t->r, l, r, res, ind+1);
	if (ind > r) return findRes(t->l, l, r, res, add);

	if (t->res == res) return t->v;
	else if (maiorRes(t->l) == res && add+sz(t->l->l) >= l) return findRes(t->l, l, r, res, add);
	return findRes(t->r, l, r, res, add);
}

int back[maxn];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) 
{
	node *t = NULL;

	for (int i = 0; i < N-1; i++)
	{
		insert(t, i, K[i], 0);
		back[K[i]] = i;
	}

	insert(t, N-1, N, 0);
	back[N] = N-1;

	int ans = 0, pos = 0;

	for (int i = 0; i < C; i++)
	{
		int l = S[i], r = E[i];

		int mx = query(t, l, r-1, 0);
		int mr = query(t, l, r, 1);
		
		if (mr > ans)
		{
			ans = mr;
			pos = back[findRes(t, l, r, mr)];
		}

		if (mx > R)
		{
			int ant = findV(t, l, r-1, mx);

			erase(t, l, r);
			insert(t, l, mx, ant);
		}
		else
		{
			int ant = findRes(t, l, r, mr);
			
			erase(t, l, r);
			insert(t, l, ant, mr+1);
		}
	}

	int mr = query(t, 0, t->sz-1, 1);

	if (mr > ans) pos = back[findRes(t, 0, t->sz-1, mr)];

	return pos;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51