oj.uz

답안 #286460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286460 2020-08-30T12:32:27 Z TMJN 마상시합 토너먼트 (IOI12_tournament) C++17
100 / 100
 118 ms 13388 KB 
#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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 6 ms 1408 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 6 ms 1536 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 6 ms 1408 KB Output is correct
8 Correct 5 ms 1408 KB Output is correct
9 Correct 3 ms 1152 KB Output is correct
10 Correct 7 ms 1536 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 5180 KB Output is correct
2 Correct 115 ms 13388 KB Output is correct
3 Correct 37 ms 6648 KB Output is correct
4 Correct 114 ms 13212 KB Output is correct
5 Correct 110 ms 12792 KB Output is correct
6 Correct 109 ms 10744 KB Output is correct
7 Correct 118 ms 13260 KB Output is correct
8 Correct 117 ms 13176 KB Output is correct
9 Correct 28 ms 6144 KB Output is correct
10 Correct 35 ms 6520 KB Output is correct