Submission #577198

#	Time	Username	Problem	Language	Result	Execution time	Memory
577198		WongChun1234	Jousting tournament (IOI12_tournament)	C++14	100 / 100	624 ms	25928 KiB

tournament

//#include"grader.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int N=100050;
int n,c,r,a[N<<1],s[N<<1],e[N],lift[25][N<<1],mxup[N<<1],cnt[N<<2],par[N<<1],seg[N<<2],cb=0,cbx=1;
bool clr[N<<2];
set<pair<int,int>> currrange;
vector<pair<int,int>> ndel;
void build(int id,int l,int r){
	if (l==r){
		cnt[id]=1;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid); build(id*2+1,mid+1,r);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
void pushdown(int id){
	cnt[id]=0; clr[id]=1;
}
int query(int id,int l,int r,int q){
	if (l==r) return l;
	int mid=(l+r)/2;
	if (clr[id]) pushdown(id*2),pushdown(id*2+1);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
	clr[id]=0;
	if (cnt[id*2]>=q) return query(id*2,l,mid,q);
	else return query(id*2+1,mid+1,r,q-cnt[id*2]);
}
void fix(int id,int l,int r,int ql,int qr){
	if (ql>r||qr<l) return;
	if (ql<=l&&qr>=r){
		pushdown(id);
		return;
	}
	int mid=(l+r)/2;
	fix(id*2,l,mid,ql,qr); fix(id*2+1,mid+1,r,ql,qr);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
void add(int id,int l,int r,int q){
	if (q>r||q<l) return;
	if (l==r){
		cnt[id]=1;
		return;
	}
	if (clr[id]) pushdown(id*2),pushdown(id*2+1);
	clr[id]=0;
	int mid=(l+r)/2;
	add(id*2,l,mid,q); add(id*2+1,mid+1,r,q);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
void bmin(int id,int l,int r){
	if (l==r){
		seg[id]=a[l-1];
		return;
	}
	int mid=(l+r)/2;
	bmin(id*2,l,mid); bmin(id*2+1,mid+1,r);
	seg[id]=max(seg[id*2],seg[id*2+1]);
}
int qmx(int id,int l,int r,int ql,int qr){
	if (ql>r||qr<l) return INT_MIN;
	if (ql<=l&&qr>=r) return seg[id];
	int mid=(l+r)/2;
	return max(qmx(id*2,l,mid,ql,qr),qmx(id*2+1,mid+1,r,ql,qr));
}
int GetBestPosition(int _N, int C, int R, int *K, int *S, int *E) {
	n=_N; c=C;
	for (int i=0;i<n-1;i++) a[i]=K[i];
	build(1,1,n+1);
	for (int i=1;i<=n;i++) currrange.insert({i,i});
	for (int i=0;i<c;i++){
		int ll=query(1,1,n+1,S[i]+1),rr=query(1,1,n+1,E[i]+2)-1;
		fix(1,1,n+1,ll,rr);
		add(1,1,n+1,ll);
		s[n+i+1]=ll; e[n+i+1]=rr;
		ndel.clear();
		for (auto ff=currrange.upper_bound({ll,-1});ff!=currrange.upper_bound({rr+1,-1});ff++){
			ndel.push_back(*ff);
			par[(*ff).second]=n+i+1;
		}
		for (auto j:ndel) currrange.erase(j);
		currrange.insert({ll,n+i+1});
	}
	for (int j=0;j<=16;j++) lift[j][n+c]=n+c;
	for (int i=n+c-1;i>=1;i--){
		mxup[i]=mxup[par[i]]+1;
		lift[0][i]=par[i];
		for (int j=1;j<=16;j++) lift[j][i]=lift[j-1][lift[j-1][i]];
	}
	bmin(1,1,n-1);
	for (int i=1;i<=n;i++){
		int curr=i,val=0;
		for (int j=16;j>=0;j--){
			//if (j==20) cerr<<curr<<":"<<s[lift[j][curr]]<<"-"<<e[lift[j][curr]]<<" "<<qmx(1,1,n-1,s[lift[j][curr]],i-1)<<","<<qmx(1,1,n-1,i,e[lift[j][curr]]-1)<<"\n";
			if (R>max(qmx(1,1,n-1,s[lift[j][curr]],i-1),qmx(1,1,n-1,i,e[lift[j][curr]]-1))) curr=lift[j][curr],val+=(1<<j);
		}
		if (val>cb) cb=val,cbx=i;
	}
	return cbx-1;
}

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