Submission #861608

#	Time	Username	Problem	Language	Result	Execution time	Memory
861608		Pyqe	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	2760 ms	1842060 KiB

soccer

#include <bits/stdc++.h>
#include "soccer.h"
 
using namespace std;
 
#define mp make_pair
#define fr first
#define sc second
 
int n,ht[2069],lg2[2069],dp[8000069],dsu[8000069],z=0;
bitset<2069> a[2069];
pair<pair<int,int>,pair<int,int>> ky[8000069];
pair<int,int> sp[2][2069][11][2069];
vector<pair<int,int>> al[8000069],al2[8000069];
bitset<8000069> vtd;
 
inline int god(int xx,int x,int y)
{
	return xx*n*n+(x-1)*n+y;
}
 
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});
}
 
int fd(int x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}
 
inline int dnc(int xx,int x,int lb,int rb)
{
	if(lb<=rb)
	{
		int u,k,l,p,p2,e,clb,crb;
		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=god(xx,x,tmp.sc);
			ky[p]={{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);
			p2=god(!xx,x-(tmp.fr-1)*u,tmp2.sc);
			if(tmp2.fr!=tmp.fr)
			{
				ae(p,p2);
			}
			else
			{
				dsu[fd(p2)]=fd(p);
			}
		}
		return p;
	}
	else
	{
		return -1;
	}
}
 
void dfs(int x)
{
	int i,sz=al2[x].size(),l,w,lb,rb,lb2,rb2;
	
	vtd[x]=1;
	dp[x]=0;
	for(i=0;i<sz;i++)
	{
		l=al2[x][i].fr;
		w=al2[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,l,w,sz;
	
	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(i=1;i<=n*n*2;i++)
	{
		dsu[i]=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<=n*n*2;i++)
	{
		sz=al[i].size();
		for(j=0;j<sz;j++)
		{
			l=al[i][j].fr;
			w=al[i][j].sc;
			al2[fd(i)].push_back({fd(l),w});
		}
	}
	for(i=1;i<=n*n*2;i++)
	{
		if(ky[i].fr.fr&&!vtd[i])
		{
			dfs(i);
		}
	}
	return z;
}

Compilation message (stderr)

soccer.cpp: In function 'void spbd(int, int)':
soccer.cpp:34:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |    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: 30 / 30