Submission #139939

#	Time	Username	Problem	Language	Result	Execution time	Memory
139939		MvC	Jousting tournament (IOI12_tournament)	C++11	49 / 100	1073 ms	10236 KiB

tournament

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "tournament.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,s[nmax],e[nmax],st[4*nmax],rs[nmax],mn[nmax],j,t,x,y,r,c,a[nmax],mx,id,l,fw[nmax],p[nmax];
vector<pair<int,int> >lb[nmax],rb[nmax];
vector<int>vc[nmax];
void upd(int x,int l,int r,int p,int v)
{
	if(l==r)
	{
		st[x]=min(st[x],v);
		return;
	}
	int mid=(l+r)/2;
	if(mid>=p)upd(2*x,l,mid,p,v);
	else upd(2*x+1,mid+1,r,p,v);
	st[x]=min(st[2*x],st[2*x+1]);
}
int qry(int x,int l,int r,int tl,int tr)
{
	if(l>tr || r<tl)return inf;
	if(tl<=l && r<=tr)return st[x];
	int mid=(l+r)/2;
	return min(qry(2*x,l,mid,tl,tr),qry(2*x+1,mid+1,r,tl,tr));
}
void upd(int i,int v)
{
	for(;i<=n;i+=i&(-i))fw[i]+=v;
}
int qry(int i)
{
	int ans=0;
	for(;i>=1;i-=i&(-i))ans+=fw[i];
	return ans;
}
int GetBestPosition(int N,int C,int R,int K[],int S[],int E[])
{
	n=N,c=C,r=R+1;
	for(i=1;i<n;i++)a[i]=K[i-1]+1;
	for(i=1;i<=c;i++)
	{
		s[i]=S[i-1]+1;
		e[i]=E[i-1]+1;
	}
	for(i=1;i<=n;i++)p[i]=i;
	for(i=1;i<=c;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(p[j]==s[i])
			{
				x=j;
				break;
			}
		}
		for(j=n;j>=1;j--)
		{
			if(p[j]==e[i])
			{
				y=j;
				break;
			}
		}
		s[i]=x,e[i]=y;
		for(j=y+1;j<=n;j++)p[j]-=(p[y]-p[x]);
		for(j=x;j<=y;j++)p[j]=p[x];
		lb[x].pb(mkp(y,i));
		rb[y].pb(mkp(x,i));
	}
	for(i=1;i<=4*n;i++)st[i]=c;
	j=1,l=0;
	for(i=1;i<=n;i++)
	{
		for(;j<=l;j++)
		{
			for(t=0;t<lb[j].size();t++)
			{
				upd(1,1,n,lb[j][t].fr,lb[j][t].sc);
			}
		}
		mn[i]=qry(1,1,n,i,n);
		if(a[i]>r)l=i;
	}
	for(i=1;i<=4*n;i++)st[i]=c;
	j=n,l=n+1;
	for(i=n;i>=1;i--)
	{
		if(a[i]>r)l=i;
		for(;j>l;j--)
		{
			for(t=0;t<rb[j].size();t++)
			{
				upd(1,1,n,rb[j][t].fr,rb[j][t].sc);
			}
		}
		mn[i]=min(mn[i],qry(1,1,n,1,i));
		vc[mn[i]].pb(i);
	}
	for(i=1;i<=c;i++)
	{
		for(j=0;j<vc[i].size();j++)
		{
			rs[vc[i][j]]=qry(vc[i][j]);
		}
		upd(s[i],1);
		upd(e[i]+1,-1);
	}
	mx=-1;
	for(i=1;i<=n;i++)
	{
		if(mx<rs[i])
		{
			mx=rs[i];
			id=i;
		}
	}
	return id-1;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>c>>r;
	r++;
	for(i=1;i<n;i++)
	{
		cin>>a[i];
		a[i]++;
	}
	for(i=1;i<=c;i++)
	{
		cin>>s[i]>>e[i];
		s[i]++,e[i]++;
	}
	for(i=1;i<=n;i++)p[i]=i;
	for(i=1;i<=c;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(p[j]==s[i])
			{
				x=j;
				break;
			}
		}
		for(j=n;j>=1;j--)
		{
			if(p[j]==e[i])
			{
				y=j;
				break;
			}
		}
		s[i]=x,e[i]=y;
		for(j=y+1;j<=n;j++)p[j]-=(p[y]-p[x]);
		for(j=x;j<=y;j++)p[j]=p[x];
		lb[x].pb(mkp(y,i));
		rb[y].pb(mkp(x,i));
		//cout<<x<<" "<<y<<endl;
	}
	for(i=1;i<=4*n;i++)st[i]=c;
	j=1,l=0;
	for(i=1;i<=n;i++)
	{
		for(;j<=l;j++)
		{
			for(t=0;t<lb[j].size();t++)
			{
				upd(1,1,n,lb[j][t].fr,lb[j][t].sc);
			}
		}
		mn[i]=qry(1,1,n,i,n);
		//cout<<mn[i]<<endl;
		if(a[i]>r)l=i;
	}
	for(i=1;i<=4*n;i++)st[i]=c;
	j=n,l=n+1;
	for(i=n;i>=1;i--)
	{
		if(a[i]>r)l=i;
		for(;j>l;j--)
		{
			for(t=0;t<rb[j].size();t++)
			{
				upd(1,1,n,rb[j][t].fr,rb[j][t].sc);
			}
		}
		mn[i]=min(mn[i],qry(1,1,n,1,i));
		cout<<mn[i]<<endl;
		vc[mn[i]].pb(i);
	}
	cout<<l<<endl;
	for(i=1;i<=c;i++)
	{
		for(j=0;j<vc[i].size();j++)
		{
			rs[vc[i][j]]=qry(vc[i][j]);
		}
		upd(s[i],1);
		upd(e[i]+1,-1);
	}
	mx=-1;
	for(i=1;i<=n;i++)
	{
		if(mx<rs[i])
		{
			mx=rs[i];
			id=i;
		}
	}
	cout<<mx<<" "<<id<<endl;
    return 0;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/

Compilation message (stderr)

tournament.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
tournament.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
tournament.cpp:234:1: warning: "/*" within comment [-Wcomment]
 /*
  
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:94:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(t=0;t<lb[j].size();t++)
            ~^~~~~~~~~~~~~
tournament.cpp:109:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(t=0;t<rb[j].size();t++)
            ~^~~~~~~~~~~~~
tournament.cpp:119:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vc[i].size();j++)
           ~^~~~~~~~~~~~~

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