Submission #986352

#	Time	Username	Problem	Language	Result	Execution time	Memory
986352		Pyqe	Jousting tournament (IOI12_tournament)	C++17	100 / 100	97 ms	49576 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,a[100069],fw[100069],fi,pr[200069][18],sr[100069],sp[17][100069],lg2[100069];
pair<long long,long long> rg[100069];

void ud(long long x,long long w)
{
	for(fi=x;fi<=n;fi+=fi&-fi)
	{
		fw[fi]+=w;
	}
}

long long bl(long long x)
{
	long long i,sm=0;
	
	fi=0;
	for(i=16;i+1;i--)
	{
		if((fi|1ll<<i)<=n&&sm+fw[fi|1ll<<i]<x)
		{
			fi|=1ll<<i;
			sm+=fw[fi];
		}
	}
	return fi+!!x;
}

void spbd()
{
	long long i,j,k;
	
	for(i=1;1ll<<i<n;i++)
	{
		for(j=1;j<n-(1ll<<i)+1;j++)
		{
			sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
		}
	}
	for(i=1;i<n;i++)
	{
		for(k=i;k>1;k/=2,lg2[i]++);
	}
}

long long spqr(long long lh,long long rh)
{
	long long e=lg2[rh-lh+1];
	
	return max(sp[e][lh],sp[e][rh-(1ll<<e)+1]);
}

int GetBestPosition(int on,int m,int d,int *aa,int *ka,int *la)
{
	long long i,j,k,l,p,lh,rh,md,zz,sm,e;
	pair<long long,long long> z={-1,-1};
	
	n=on;
	d++;
	for(i=1;i<n;i++)
	{
		a[i]=aa[i-1]+1;
		sp[0][i]=a[i];
	}
	for(i=1;i<=n;i++)
	{
		ud(i,1);
		sr[i]=i;
	}
	for(i=1;i<=m;i++)
	{
		k=ka[i-1]+1;
		l=la[i-1]+1;
		for(j=l;j>=k;j--)
		{
			p=bl(j);
			if(j<l)
			{
				ud(p,-1);
			}
			pr[sr[p]][0]=n+i;
		}
		p=bl(k);
		rg[i]={bl(k-1)+1,p};
		sr[p]=n+i;
	}
	for(i=n+m;i;i--)
	{
		for(j=1;j<18;j++)
		{
			pr[i][j]=pr[pr[i][j-1]][j-1];
		}
	}
	spbd();
	for(i=1;i<=n;i++)
	{
		for(zz=i,lh=1,rh=i-1;lh<=rh;)
		{
			md=(lh+rh)/2;
			if(spqr(md,i-1)<d)
			{
				zz=md;
				rh=md-1;
			}
			else
			{
				lh=md+1;
			}
		}
		k=zz;
		for(zz=i-1,lh=i,rh=n-1;lh<=rh;)
		{
			md=(lh+rh)/2;
			if(spqr(i,md)<d)
			{
				zz=md;
				lh=md+1;
			}
			else
			{
				rh=md-1;
			}
		}
		l=zz+1;
		sm=0;
		p=i;
		for(j=17;j+1;j--)
		{
			if(pr[p][j]&&rg[pr[p][j]-n].fr>=k&&rg[pr[p][j]-n].sc<=l)
			{
				sm|=1ll<<j;
				p=pr[p][j];
			}
		}
		z=max(z,{sm,-i});
	}
	e=-z.sc;
	return e-1;
}

Compilation message (stderr)

tournament.cpp: In function 'void spbd()':
tournament.cpp:44:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |    sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
      |                                            ~^~

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