Submission #282554

#	Time	Username	Problem	Language	Result	Execution time	Memory
282554		amiratou	Jousting tournament (IOI12_tournament)	C++14	100 / 100	385 ms	52588 KiB

tournament

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
const int MX = 100005, INF = (int)(1e9) , L = 18;
typedef pair<int,int> ii;

int fen[MX],Ry[MX],up[2*MX][L],d[2*MX],ST[4*MX],KK[MX],n,ans=-1,ARG;
int sp[MX][L];
vector<int> vec[2*MX];
ii ranges[2*MX];
void update(int idx,int val){
	for (int i = idx; i <= n; i+=(i&(-i)))
		fen[i]+=val;
}
int get(int idx){
	int h=0;
	for (int i = idx; i >= 1; i-=(i&(-i)))
		h+=fen[i];
	return h;
}
int gimme(int nb,int l=0,int r=n-1){
	int ans=-1;
	while(l<=r){
		int med=(l+r)>>1;
		if(get(med+1)>=nb)
			ans=med,r=med-1;
		else l=med+1;
	}
	assert(ans!=-1);
	return ans;
}
void dfs(int node,int p){
	up[node][0]=p;
	for (int i = 1; i < L; ++i)
		up[node][i]=up[up[node][i-1]][i-1];
	for(auto it:vec[node])
		d[it]=d[node]+1,dfs(it,node);
}
int L_2(int x){
	return 31-__builtin_clz(x);
}
int query(int a,int b){
	int h=L_2(b-a+1);
	return max(sp[a][h],sp[b-(1<<h)+1][h]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	set<int> alive;
	set<pair<ii,int> > myset;
	n=N;
	for (int i = 0; i < N; ++i)
	{
		sp[i][0]=K[i];
		up[i+C][0]=-1;
		ranges[C+i]={i,i};
		if(i!=(N-1))KK[i]=K[i];
		myset.insert({{i,-i},C+i});
		alive.insert(i);
		update(i+1,1),Ry[i]=i;
	}
	for (int i = 1; i < L; ++i)
		for (int j = 0; j+(1<<i)-1 < N; ++j)
			sp[j][i]=max(sp[j][i-1],sp[j+(1<<(i-1))][i-1]);
	for (int i = 0; i < C; ++i)
	{
		up[i][0]=-1;
		int st=gimme(S[i]+1),e=gimme(E[i]+1);
		e=Ry[e];
		auto it=alive.lower_bound(st);
		while(it!=alive.end() && (*it)<=e)
			update(*it+1,-1),it=alive.erase(it);
		update(st+1,1),alive.insert(st),Ry[st]=e;
		ranges[i]={st,e};
		myset.insert({{st,-e},i});
	}
	vector<int> order;
	while(!myset.empty()){
		pair<ii,int> it=*myset.begin();
		order.push_back(it.se);
		myset.erase(myset.begin());
		it.fi.se*=-1;
		auto k=myset.begin();
		while(k!=myset.end() && (-(*k).fi.se)<=it.fi.se){
			vec[it.se].push_back(k->se);
			k=myset.lower_bound({{-(*k).fi.se+1,-INF},-1});
		}
	}
	for(auto it:order)
		if(up[it][0]==-1)dfs(it,it);
	for (int i = 0; i < N; ++i)
	{
		int l=1,r=d[C+i],nb=0;
		while(l<=r){
			int med=(l+r)>>1,node=C+i;
			for (int j = 0; j < L; ++j)
				if((med>>j)&1)node=up[node][j];
			assert(node<C);
			int maxi=-1;
			if(i!=ranges[node].fi)maxi=max(maxi,query(ranges[node].fi,i-1));
			if(i!=ranges[node].se)maxi=max(maxi,query(i,ranges[node].se-1));
			if(maxi<R)nb=med,l=med+1;
			else r=med-1;
		}
		if(nb>ans)ans=nb,ARG=i;
	}
	return ARG;
}

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