Submission #59257

#	Time	Username	Problem	Language	Result	Execution time	Memory
59257		TadijaSebez	Jousting tournament (IOI12_tournament)	C++11	100 / 100	400 ms	54020 KiB

tournament

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define pb push_back
const int N=100050;
const int M=2*N;
int root;
vector<int> E[M];
int node[N];
set<int> play;
int ls[M],rs[M],sum[M],tsz,rt;
void Set(int &c, int ss, int se, int qi, int val)
{
	if(!c) c=++tsz;
	sum[c]+=val;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,val);
	else Set(rs[c],mid+1,se,qi,val);
}
int Get(int c, int ss, int se, int k)
{
	if(ss==se) return ss;
	int mid=ss+se>>1;
	if(sum[ls[c]]>=k) return Get(ls[c],ss,mid,k);
	else return Get(rs[c],mid+1,se,k-sum[ls[c]]);
}
int csz[M],head[M],dep[M],sz[M],par[M][18];
void DFS(int u, int p)
{
	par[u][0]=p;
	dep[u]=dep[p]+1;
	sz[u]=1;
	int i;
	for(i=1;i<18;i++) par[u][i]=par[par[u][i-1]][i-1];
	for(i=0;i<E[u].size();i++) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
}
void HLD(int u)
{
	csz[head[u]]++;
	int i,HC=0;
	for(i=0;i<E[u].size();i++) if(sz[E[u][i]]>sz[HC]) HC=E[u][i];
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v==HC) head[v]=head[u];
		else head[v]=v;
		HLD(v);
	}
}
vector<int> bit[M];
void Add(int j, int i, int f){ for(;i;i-=i&-i) bit[j][i]+=f;}
int Get(int j, int i){ int ret=0;for(;i<bit[j].size();i+=i&-i) ret+=bit[j][i];return ret;}
void Set(int u, int f)
{
	while(u)
	{
		int id=dep[u]-dep[head[u]]+1;
		Add(head[u],id,f);
		u=par[head[u]][0];
	}
}
int Get(int u){ return Get(head[u],dep[u]-dep[head[u]]+1);}
int GetKth(int u, int k){ for(int i=0;i<18;i++) if((k>>i)&1) u=par[u][i];return u;}
int push[N];
int GetBestPosition(int n, int m, int rank, int *a, int *s, int *e)
{
	int i,j;
	root=n;
	for(i=0;i<n;i++) node[i]=i+1,play.insert(i),Set(rt,0,n-1,i,1);
	for(j=0;j<m;j++)
	{
		int l=Get(rt,0,n-1,s[j]+1);
		int r=Get(rt,0,n-1,e[j]+1);
		//printf("%i %i\n",l,r);
		root++;
		set<int>::iterator it;
		bool fir=1;
		for(it=play.lower_bound(l);it!=play.upper_bound(r);it++)
		{
			E[root].pb(node[*it]);
			//printf("%i -> %i\n",root,node[*it]);
			if(!fir) Set(rt,0,n-1,*it,-1);
			fir=0;
		}
		node[*play.lower_bound(l)]=root;
		play.erase(play.upper_bound(l),play.upper_bound(r));
	}
	//printf(":D\n");
	DFS(root,0);
	head[root]=root;
	HLD(root);
	for(i=1;i<=root;i++) bit[i].resize(csz[i]+1);
	for(i=2;i<=n;i++)
	{
		if(rank<a[i-2]) Set(i,1),push[i]=1;
	}
	int sol=-1,ans=-1;
	for(i=1;i<=n;i++)
	{
		int top=dep[i]-1,bot=0,mid,ok=0;
		while(top>=bot)
		{
			mid=top+bot>>1;
			if(!Get(GetKth(i,mid))) ok=mid,bot=mid+1;
			else top=mid-1;
		}
		if(ans<ok) ans=ok,sol=i-1;
		if(push[i+1])
		{
			Set(i+1,-1);
			Set(i,1);
		}
	}
	return sol;
}
//--------------------//
/*
int A[N],L[N],R[N];
int main()
{
	int n,m,rank,i;
	scanf("%i %i %i",&n,&m,&rank);
	for(i=0;i<n-1;i++) scanf("%i",&A[i]);
	for(i=0;i<m;i++) scanf("%i %i",&L[i],&R[i]);
	printf("%i\n",GetBestPosition(n,m,rank,A,L,R));
	return 0;
}
*/
//--------------------//

Compilation message (stderr)

tournament.cpp: In function 'void Set(int&, int, int, int, int)':
tournament.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
tournament.cpp: In function 'int Get(int, int, int, int)':
tournament.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
tournament.cpp: In function 'void DFS(int, int)':
tournament.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
          ~^~~~~~~~~~~~
tournament.cpp: In function 'void HLD(int)':
tournament.cpp:44:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++) if(sz[E[u][i]]>sz[HC]) HC=E[u][i];
          ~^~~~~~~~~~~~
tournament.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++)
          ~^~~~~~~~~~~~
tournament.cpp: In function 'int Get(int, int)':
tournament.cpp:55:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 int Get(int j, int i){ int ret=0;for(;i<bit[j].size();i+=i&-i) ret+=bit[j][i];return ret;}
                                       ~^~~~~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:106:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~

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