Submission #861582

#	Time	Username	Problem	Language	Result	Execution time	Memory
861582		Pyqe	Soccer Stadium (IOI23_soccer)	C++17	70 / 100	4636 ms	1517772 KiB

soccer

#include <bits/stdc++.h>
#include "soccer.h"

using namespace std;

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

int n,nn,ht[2069],lg2[2069],dp[8000069],z=0;
bitset<2069> a[2069];
pair<pair<int,int>,pair<int,int>> ky[8000069];
map<pair<pair<int,int>,pair<int,int>>,int> ykmp;
pair<int,int> sp[2][2069][11][2069];
vector<pair<int,int>> al[8000069];
bitset<8000069> vtd;

inline int yk(int lb,int rb,int lb2,int rb2)
{
	int k=ykmp[{{lb,rb},{lb2,rb2}}];
	
	if(!k)
	{
		nn++;
		ky[nn]={{lb,rb},{lb2,rb2}};
		ykmp[{{lb,rb},{lb2,rb2}}]=nn;
		return nn;
	}
	else
	{
		return k;
	}
}

inline void spbd(int xx,int x)
{
	int i,j;
	
	for(i=1;i<=n;i++)
	{
		sp[xx][x][0][i]={ht[i],i};
	}
	for(i=1;1<<i<=n;i++)
	{
		for(j=1;j<=n-(1<<i)+1;j++)
		{
			sp[xx][x][i][j]=min(sp[xx][x][i-1][j],sp[xx][x][i-1][j+(1<<i-1)]);
		}
	}
}

inline pair<int,int> spqr(int xx,int x,int lb,int rb)
{
	int e=lg2[rb-lb+1];
	
	return min(sp[xx][x][e][lb],sp[xx][x][e][rb-(1<<e)+1]);
}

inline void ae(int x,int y)
{
	int w,clb,crb,lb,rb,lb2,rb2;
	
	clb=ky[x].fr.fr;
	crb=ky[x].fr.sc;
	lb=ky[y].fr.fr;
	rb=ky[y].fr.sc;
	lb2=ky[y].sc.fr;
	rb2=ky[y].sc.sc;
	w=(rb-lb-(crb-clb))*(rb2-lb2+1);
	al[x].push_back({y,w});
}

inline int dnc(int xx,int x,int lb,int rb)
{
	if(lb<=rb)
	{
		int u,k,l,p,p2,e,clb,crb,clb2,crb2;
		pair<int,int> tmp=spqr(xx,x,lb,rb),tmp2;
		
		u=!xx*2-1;
		clb=x-(tmp.fr-1)*u;
		crb=x;
		if(xx)
		{
			swap(clb,crb);
		}
		if(clb<=crb)
		{
			p=yk(clb,crb,lb,rb);
		}
		else
		{
			p=-1;
		}
		for(k=lb,l=rb;k<=l;k=e+1)
		{
			tmp2=spqr(xx,x,k,l);
			if(tmp2.fr!=tmp.fr)
			{
				break;
			}
			e=tmp2.sc;
			p2=dnc(xx,x,k,e-1);
			if(p!=-1&&p2!=-1)
			{
				ae(p,p2);
			}
		}
		p2=dnc(xx,x,k,l);
		if(p!=-1&&p2!=-1)
		{
			ae(p,p2);
		}
		if(p!=-1)
		{
			tmp2=spqr(!xx,x-(tmp.fr-1)*u,lb,rb);
			if(tmp2.fr!=tmp.fr)
			{
				clb2=x-(tmp.fr-1)*u;
				crb2=x-(tmp.fr-tmp2.fr)*u;
				if(xx)
				{
					swap(clb2,crb2);
				}
				p2=yk(clb2,crb2,lb,rb);
				ae(p,p2);
			}
		}
		return p;
	}
	else
	{
		return -1;
	}
}

void dfs(int x)
{
	int i,sz=al[x].size(),l,w,lb,rb,lb2,rb2;
	
	vtd[x]=1;
	dp[x]=0;
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		w=al[x][i].sc;
		if(!vtd[l])
		{
			dfs(l);
		}
		dp[x]=max(dp[x],dp[l]+w);
	}
	lb=ky[x].fr.fr;
	rb=ky[x].fr.sc;
	lb2=ky[x].sc.fr;
	rb2=ky[x].sc.sc;
	z=max(z,dp[x]+(rb-lb+1)*(rb2-lb2+1));
}

int biggest_stadium(int on,vector<vector<int>> oa)
{
	int i,j,ii,u,k;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			a[i][j]=oa[i-1][j-1];
		}
		for(k=i;k>1;k/=2,lg2[i]++);
	}
	for(ii=0;ii<2;ii++)
	{
		u=!ii*2-1;
		for(i=1;i<=n;i++)
		{
			ht[i]=0;
		}
		for(i=1+(n-1)*ii;i&&i<=n;i+=u)
		{
			for(j=1;j<=n;j++)
			{
				ht[j]=(ht[j]+1)*!a[i][j];
			}
			spbd(ii,i);
		}
	}
	for(ii=0;ii<2;ii++)
	{
		u=!ii*2-1;
		for(i=1+(n-1)*ii;i&&i<=n;i+=u)
		{
			dnc(ii,i,1,n);
		}
	}
	for(i=1;i<=nn;i++)
	{
		if(!vtd[i])
		{
			dfs(i);
		}
	}
	return z;
}

Compilation message (stderr)

soccer.cpp: In function 'void spbd(int, int)':
soccer.cpp:47:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |    sp[xx][x][i][j]=min(sp[xx][x][i-1][j],sp[xx][x][i-1][j+(1<<i-1)]);
      |                                                               ~^~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 0 / 30