제출 #286460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286460		TMJN	마상시합 토너먼트 (IOI12_tournament)	C++17	100 / 100	118 ms	13388 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

mt19937 mt(869120);

struct treap{
	int pri,size,range_l,range_r,type;
	treap *lch,*rch;
	treap(int l,int r,int t){
		lch=rch=NULL;
		range_l=l;
		range_r=r;
		type=t;
		pri=mt();
		size=1;
	}
	treap(){
	}
};
int size(treap *pt){
	if(pt==NULL)return 0;
	return pt->size;
}
treap* update(treap *pt){
	pt->size=size(pt->lch)+size(pt->rch)+1;
	return pt;
}
treap* merge(treap *l,treap *r){
	if(l==NULL)return r;
	else if(r==NULL)return l;
	if(l->pri>r->pri){
		l->rch=merge(l->rch,r);
		return update(l);
	}
	else{
		r->lch=merge(l,r->lch);
		return update(r);
	}
}
pair<treap*,treap*>split(treap* pt,int t){
	if(pt==NULL)return{NULL,NULL};
	if(t<=size(pt->lch)){
		auto p=split(pt->lch,t);
		pt->lch=p.second;
		return {p.first,update(pt)};
	}
	else{
		auto p=split(pt->rch,t-size(pt->lch)-1);
		pt->rch=p.first;
		return{update(pt),p.second};
	}
}

void dfs(int &l,int &r,vector<int>&v,treap*pt){
	if(pt==NULL)return;
	l=min(l,pt->range_l);
	r=max(r,pt->range_r);
	if(pt->type!=-1){
		v.push_back(pt->type);
	}
	dfs(l,r,v,pt->lch);
	dfs(l,r,v,pt->rch);
}



int tree[1<<18],A[100000],P[100000],L[100000],R[100000],V[100000];
treap tre[200000];
treap *root;

int calc(int l,int r){
	l+=1<<17;
	r+=1<<17;
	int a=-1;
	while(l<=r){
		a=max({a,tree[l],tree[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

int GetBestPosition(int N, int C, int T, int *K, int *S, int *E) {
	for(int i=0;i<N-1;i++){
		tree[i+(1<<17)]=K[i];
	}
	for(int i=(1<<17)-1;i;i--){
		tree[i]=max(tree[i+i],tree[i+i+1]);
	}
	for(int i=0;i<N;i++){
		tre[i]=treap(i,i,-1);
	}
	root=tre;
	for(int i=1;i<N;i++){
		root=merge(root,tre+i);
	}
	for(int i=0;i<C;i++){
		auto p=split(root,E[i]+1);
		auto pp=split(p.first,S[i]);
		L[i]=0xE869120;
		R[i]=-0xE869120;
		vector<int>v;
		dfs(L[i],R[i],v,pp.second);
		tre[N+i]=treap(L[i],R[i],i);
		root=merge(pp.first,merge(tre+N+i,p.second));
		for(int j:v){
			P[j]=i;
		}
	}
	P[C-1]=C-1;
	for(int i=C-1;i>=0;i--){
		V[i]=V[P[i]]+(calc(L[i],R[i]-1)<T);
	}
	pair<int,int>p={0,0};
	for(int i=0;i<C-1;i++){
		p=max(p,{V[i],-L[i]});
	}
	return -p.second;
}

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