Submission #137412

#	Time	Username	Problem	Language	Result	Execution time	Memory
137412		jangwonyoung	Jousting tournament (IOI12_tournament)	C++14	100 / 100	165 ms	10280 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
const int ts=262144;
const int N=1e5+1,Q=1e5+1;
int n,q,k;
int mn[ts];
int a[N];
int lq[Q],rq[Q];
int mj[N];
void build(int id,int l,int r){
	if(l==r) mn[id]=a[l];
	else{
		int mid=(l+r)/2;
		build(id*2,l,mid);build(id*2+1,mid+1,r);
		mn[id]=min(mn[id*2],mn[id*2+1]);
	}
}
int qry(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return 1e9;
	if(ql<=l && r<=qr) return mn[id];
	int mid=(l+r)/2;
	return min(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
int cnt[ts];
bool die[ts];
void push2(int id){
	if(!die[id]) return;
	die[id*2]=true;cnt[id*2]=0;
	die[id*2+1]=true;cnt[id*2+1]=0;
	die[id]=false;
}
void build2(int id,int l,int r){
	if(l==r) cnt[id]=1;
	else{
		int mid=(l+r)/2;
		build2(id*2,l,mid);build2(id*2+1,mid+1,r);
		cnt[id]=cnt[id*2]+cnt[id*2+1];
	}
}
void upd2(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		die[id]=true;cnt[id]=0;
		return;
	}
	push2(id);
	int mid=(l+r)/2;
	upd2(id*2,l,mid,ql,qr);
	upd2(id*2+1,mid+1,r,ql,qr);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
int qry2(int id,int l,int r,int x){
	if(l==r) return l;
	push2(id);
	int mid=(l+r)/2;
	if(cnt[id*2]>=x) return qry2(id*2,l,mid,x);
	return qry2(id*2+1,mid+1,r,x-cnt[id*2]);
}
int mx[ts],wn[ts];
int mp[ts];
bool dead[ts];
void push3(int id){
	if(!dead[id*2]) wn[id*2]+=wn[id],mx[id*2]+=wn[id];
	if(!dead[id*2+1]) wn[id*2+1]+=wn[id],mx[id*2+1]+=wn[id];
	if(dead[id]){
		dead[id*2]=dead[id*2+1]=true;
	}
	wn[id]=0;
}
void build3(int id,int l,int r){
	if(l==r) mp[id]=l;
	else{
		int mid=(l+r)/2;
		build3(id*2,l,mid);build3(id*2+1,mid+1,r);
		mp[id]=l;
	}
}
void upd3a(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		if(!dead[id]) wn[id]++,mx[id]++;
		return;
	}
	push3(id);
	int mid=(l+r)/2;
	upd3a(id*2,l,mid,ql,qr);
	upd3a(id*2+1,mid+1,r,ql,qr);
	if(mx[id*2]>=mx[id*2+1]) mx[id]=mx[id*2],mp[id]=mp[id*2];
	else mx[id]=mx[id*2+1],mp[id]=mp[id*2+1];
}
void upd3b(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		dead[id]=true;
		return;
	}
	push3(id);
	int mid=(l+r)/2;
	upd3b(id*2,l,mid,ql,qr);
	upd3b(id*2+1,mid+1,r,ql,qr);
	if(mx[id*2]>=mx[id*2+1]) mx[id]=mx[id*2],mp[id]=mp[id*2];
	else mx[id]=mx[id*2+1],mp[id]=mp[id*2+1];
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	int n=N,q=C,k=n-R;
	for(int i=1; i<n ;i++) a[i]=n-K[i-1],mj[i]=i;
	for(int i=1; i<=q ;i++) lq[i]=S[i-1]+1,rq[i]=E[i-1]+1;
	build(1,1,n);
	build2(1,1,n);
	build3(1,1,n);
	for(int i=1; i<=q ;i++){
		lq[i]=qry2(1,1,n,lq[i]);
		rq[i]=mj[qry2(1,1,n,rq[i])];
		mj[lq[i]]=rq[i];
		upd2(1,1,n,lq[i]+1,rq[i]);
		int mini=qry(1,1,n,lq[i],rq[i]-1);
		if(mini<k) upd3b(1,1,n,lq[i],rq[i]);
		else upd3a(1,1,n,lq[i],rq[i]);
	}
	return mp[1]-1;
}

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