Submission #15675

#	Time	Username	Problem	Language	Result	Execution time	Memory
15675		progressive	Jousting tournament (IOI12_tournament)	C++14	100 / 100	128 ms	9456 KiB

tournament

#include<cstring>
#include<cstdlib>
//#include<cstdio>
#include<algorithm>
using namespace std;
struct Node
{
	pair<int,int> v;
	int ansv;
	int ansi;
	int sz;
	Node *l;
	Node *r;
	Node *p;
};
Node *root;
void UpdateSize(Node *P)
{
	P->sz=1;
	if(P->l) P->sz+=P->l->sz;
	if(P->r) P->sz+=P->r->sz;
	
}
void RightRotate(Node *P)
{
	Node *T=P->l;
	Node *B=T->r;
	Node *D=P->p;
	if(D)
	{
		if(D->l==P) D->l=T;
		else D->r=T;
	}
	if(B)
		B->p=P;
	
	P->p=T;
	P->l=B;
	UpdateSize(P);
	
	T->r=P;
	T->p=D;
	UpdateSize(T);
}
void LeftRotate(Node *P)
{
	Node *T=P->r;
	Node *B=T->l;
	Node *D=P->p;
	if(D)
	{
		if(D->l==P) D->l=T;
		else D->r=T;
	}
	if(B)
		B->p=P;
	
	P->p=T;
	P->r=B;
	UpdateSize(P);
	
	T->l=P;
	T->p=D;
	UpdateSize(T);
}
void Splay(Node *P)
{
	while(P->p)
	{
		Node* PP=P->p;
		Node* PPP=PP->p;
		if(!PPP)
		{
			if(PP->l==P) RightRotate(PP);
			else LeftRotate(PP);
			break;
		}
		if(PPP->l==PP)
		{
			if(PP->l==P)
			{
				RightRotate(PPP);
				RightRotate(PP);
			}
			else
			{
				LeftRotate(PP);
				RightRotate(PPP);
			}
		}
		else
		{
			if(PP->l==P)
			{
				RightRotate(PP);
				LeftRotate(PPP);
			}
			else
			{
				LeftRotate(PPP);
				LeftRotate(PP);
			}
		}
	}
	root=P;
}
void Insert(pair<int, int> v,int ansv,int ansi)
{
	Node *T=root;
	if(!T)
	{
		root=(Node*) malloc(sizeof(Node));
		root->l=NULL;
		root->r=NULL;
		root->p=NULL;
		root->v=v;
		root->sz=1;
		root->ansv=ansv;
		root->ansi=ansi;
		return;
	}
	while(T)
	{
		if(v < (T->v) )
		{
			if(T->l)
			{
				T=T->l;
				continue;
			}
			else
			{
				T->l=(Node *)malloc(sizeof(Node));
				T->l->l=NULL;
				T->l->r=NULL;
				T->l->p=T;
				T->l->v=v;
				T->l->ansv=ansv;
				T->l->ansi=ansi;
				T->l->sz=1;
				T=T->l;
				break;
			}
		}
		else
		{
			if(T->r)
			{
				T=T->r;
				continue;
			}
			else
			{
				T->r=(Node *)malloc(sizeof(Node));
				T->r->l=NULL;
				T->r->r=NULL;
				T->r->p=T;
				T->r->v=v;
				T->r->ansv=ansv;
				T->r->ansi=ansi;
				T->r->sz=1;
				T=T->r;
				break;
			}
		}
	}
	Node* tosplay=T;
	while(T)
	{
		UpdateSize(T);
		T=T->p;
	}
	Splay(tosplay);
}

Node* Find(pair<int,int> v)
{
	Node *T=root;
	while(T)
	{
		if(v==(T->v))
		{
			Splay(T);
			return T;
		}
		if(v< (T->v))
		{
			if(T->l)
			{
				T=T->l;
			}
			else
			{
				Splay(T);
				return NULL;
			}
		}
		else
		{
			if(T->r)
			{
				T=T->r;
			}
			else
			{
				Splay(T);
				return NULL;
			}
		}
	}
	return NULL;
}

void Erase(Node *T)
{
	Splay(T);
	
	if(T->l)
	{
		root=T->l;
		Node *x=root;
		while(x->r) x=x->r;
		x->r=T->r;
		if(T->r) T->r->p=x;
		while(x->p)
		{
			UpdateSize(x);
			x=x->p;
		}
	}
	else
		root=T->r;
	free(T);
	if(root)root->p=NULL;
}

Node* findKth(Node *T,int K)
{
	int sz=0;
	if(T->l) sz=T->l->sz;
	if(sz==K) return T;
	if(sz>K)
		return findKth(T->l,K);
	else
		return findKth(T->r,K-sz-1);
}
Node* findKth(int K)
{
	Node* Kth=findKth(root,K);
	Splay(Kth);
	return Kth;
}
int R;
const int MAXN=131072;
int idx[MAXN*2];
int getmax(int l,int r)
{
	l+=MAXN;
	r+=MAXN;
	int ans=0;
	while(l<=r)
	{
		if(l%2==1)
			ans=max(ans,idx[l++]);
		if(r%2==0)
			ans=max(ans,idx[r--]);
		l/=2;
		r/=2;
	}
	return ans;
}
void Query(int A,int B) //from Ath Node to Bth Node (0-based)
{
	int findcount=B-A+1;
	Node *Ath=findKth(A);
	Node *Bth=findKth(B);
	//printf("%d %d %d %d\n",A,B,(Ath->v).first,(Bth->v).first);
	int ansv=-1;
	int ansi=-1;
	pair<int,int> v=make_pair((Ath->v).first,(Bth->v).second);
	//printf("%d\n",root->sz);
	for(int i=0;i<findcount;i++)
	{
	//	printf("%d %d\n",root->sz,A);
		Node *Ath=findKth(A);
		if(ansv < (Ath->ansv))
		{
			ansv=Ath->ansv;
			ansi=Ath->ansi;
		}
		//printf("%d\n",root->sz);
		Erase(Ath);
	}
	//puts("ok");
	int ans=getmax(v.first,v.second-1);
	
	if(ans<R) ansv++;
	Insert(v,ansv,ansi);
}


int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
	::R=R;
	for(int i=0;i<N;i++)
		Insert(make_pair(i,i),0,i);
	for(int i=0;i<N-1;i++)
		idx[MAXN+i]=K[i];
	for(int i=MAXN-1;i>=1;i--)
		idx[i]=max(idx[2*i],idx[2*i+1]);
	for(int i=0;i<C;i++)
		Query(S[i],E[i]);
	return root->ansi;	
}

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