Submission #282372

#	Time	Username	Problem	Language	Result	Execution time	Memory
282372		amiratou	Jousting tournament (IOI12_tournament)	C++14	100 / 100	946 ms	46700 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;
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);
}
void build(int node,int l,int r){
	if(l==r){
		ST[node]=KK[l];
		return;
	}
	int med=(l+r)>>1;
	build(node*2,l,med),build(node*2+1,med+1,r);
	ST[node]=max(ST[node*2],ST[node*2+1]);
}
int query(int node,int l,int r,int i,int j){
	if(l>j || r<i)return -1;
	if(l>=i && r<=j)return ST[node];
	int med=(l+r)>>1;
	return max(query(node*2,l,med,i,j),query(node*2+1,med+1,r,i,j));
}

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)
	{
		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 = 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);
	build(1,0,N-2);
	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(1,0,n-2,ranges[node].fi,i-1));
			if(i!=ranges[node].se)maxi=max(maxi,query(1,0,n-2,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