Submission #544842

#	Time	Username	Problem	Language	Result	Execution time	Memory
544842		MilosMilutinovic	Jousting tournament (IOI12_tournament)	C++14	0 / 100	42 ms	5200 KiB

tournament

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}

int a[100005],fnw[100005],sl[100005],sr[100005],fa[100005],dep[100005];

int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}

void modify(int x,int v){
	for(;x<100005;x+=x&-x)fnw[x]+=v;
}

int query(int x){
	int i=0;
	for(int b=20;b>=0;b--)if(i+(1<<b)<100005&&x>fnw[i+(1<<b)])i+=(1<<b),x-=fnw[i];
	return i+1;
}

int GetBestPosition(int N,int C,int R,int*K,int*S,int*E){
	a[1]=R;
	for(int i=2;i<=N;i++)a[i]=K[i-2];
	for(int i=1;i<=N;i++)a[i]=(a[i]>R?1:0);
	set<int> st;
	for(int i=1;i<=N;i++)modify(i,1),st.insert(i);
	for(int i=1;i<=N;i++)sl[i]=sr[i]=fa[i]=i;
	for(int i=N+1;i<=N+C;i++)fa[i]=i,sl[i]=N+C,sr[i]=0;
	for(int i=1;i<=C;i++){
		int l=query(S[i]+1),r=query(E[i]+1);
		while(1){
			auto it=st.lower_bound(l);
			if(it==st.end()||*it>r)break;
			chkmax(dep[N+i],dep[getf(*it)]);
			chkmin(sl[N+i],sl[getf(*it)]);
			chkmax(sr[N+i],sr[getf(*it)]);
			modify(*it,-1);
			st.erase(it);
		}
		fa[getf(l)]=N+i;
		dep[N+i]++;
	}
	int ans=0,pos=1;
	for(int i=1;i<=N;i++)a[i]=a[i-1]+a[i];
	for(int i=N+1;i<=N+C;i++)if(a[sr[i]]==a[sl[i]]&&ans<dep[i])ans=dep[i],pos=sr[i];
	return pos-1;
}

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