oj.uz

Submission #861580

# Submission time Handle Problem Language Result Execution time Memory
861580 2023-10-16T13:48:12 Z Pyqe Soccer Stadium (IOI23_soccer) C++17
36 / 100
 4500 ms 921748 KB 
#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;
	
	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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 197204 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 195152 KB ok
2 Correct 41 ms 195372 KB ok
3 Correct 41 ms 197212 KB ok
4 Correct 40 ms 197200 KB ok
5 Correct 41 ms 195352 KB ok
6 Correct 42 ms 195152 KB ok
7 Correct 49 ms 230236 KB ok
8 Correct 87 ms 304660 KB ok
9 Correct 679 ms 921748 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 195152 KB ok
2 Correct 41 ms 195372 KB ok
3 Correct 40 ms 195156 KB ok
4 Correct 41 ms 195356 KB ok
5 Correct 40 ms 195316 KB ok
6 Correct 40 ms 195212 KB ok
7 Correct 40 ms 195156 KB ok
8 Correct 40 ms 195220 KB ok
9 Correct 41 ms 195420 KB ok
10 Correct 40 ms 195164 KB ok
11 Correct 39 ms 195156 KB ok
12 Correct 40 ms 195152 KB ok
13 Correct 40 ms 195376 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 197204 KB ok
2 Correct 39 ms 195152 KB ok
3 Correct 41 ms 195372 KB ok
4 Correct 40 ms 195156 KB ok
5 Correct 41 ms 195356 KB ok
6 Correct 40 ms 195316 KB ok
7 Correct 40 ms 195212 KB ok
8 Correct 40 ms 195156 KB ok
9 Correct 40 ms 195220 KB ok
10 Correct 41 ms 195420 KB ok
11 Correct 40 ms 195164 KB ok
12 Correct 39 ms 195156 KB ok
13 Correct 40 ms 195152 KB ok
14 Correct 40 ms 195376 KB ok
15 Correct 40 ms 197204 KB ok
16 Correct 41 ms 197468 KB ok
17 Correct 40 ms 197208 KB ok
18 Correct 41 ms 197468 KB ok
19 Correct 40 ms 197208 KB ok
20 Correct 40 ms 197208 KB ok
21 Correct 39 ms 197416 KB ok
22 Correct 42 ms 197436 KB ok
23 Correct 40 ms 197208 KB ok
24 Correct 41 ms 197200 KB ok
25 Correct 41 ms 197212 KB ok
26 Correct 41 ms 197212 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 197204 KB ok
2 Correct 39 ms 195152 KB ok
3 Correct 41 ms 195372 KB ok
4 Correct 41 ms 197212 KB ok
5 Correct 40 ms 197200 KB ok
6 Correct 40 ms 195156 KB ok
7 Correct 41 ms 195356 KB ok
8 Correct 40 ms 195316 KB ok
9 Correct 40 ms 195212 KB ok
10 Correct 40 ms 195156 KB ok
11 Correct 40 ms 195220 KB ok
12 Correct 41 ms 195420 KB ok
13 Correct 40 ms 195164 KB ok
14 Correct 39 ms 195156 KB ok
15 Correct 40 ms 195152 KB ok
16 Correct 40 ms 195376 KB ok
17 Correct 40 ms 197204 KB ok
18 Correct 41 ms 197468 KB ok
19 Correct 40 ms 197208 KB ok
20 Correct 41 ms 197468 KB ok
21 Correct 40 ms 197208 KB ok
22 Correct 40 ms 197208 KB ok
23 Correct 39 ms 197416 KB ok
24 Correct 42 ms 197436 KB ok
25 Correct 40 ms 197208 KB ok
26 Correct 41 ms 197200 KB ok
27 Correct 41 ms 197212 KB ok
28 Correct 41 ms 197212 KB ok
29 Correct 40 ms 197468 KB ok
30 Correct 43 ms 205656 KB ok
31 Correct 42 ms 205652 KB ok
32 Correct 42 ms 205648 KB ok
33 Correct 42 ms 205656 KB ok
34 Correct 41 ms 205616 KB ok
35 Correct 43 ms 205660 KB ok
36 Correct 42 ms 205660 KB ok
37 Correct 43 ms 205648 KB ok
38 Correct 43 ms 205656 KB ok
39 Correct 43 ms 205648 KB ok
40 Correct 42 ms 205660 KB ok
41 Execution timed out 4598 ms 205628 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 197204 KB ok
2 Correct 39 ms 195152 KB ok
3 Correct 41 ms 195372 KB ok
4 Correct 41 ms 197212 KB ok
5 Correct 40 ms 197200 KB ok
6 Correct 40 ms 195156 KB ok
7 Correct 41 ms 195356 KB ok
8 Correct 40 ms 195316 KB ok
9 Correct 40 ms 195212 KB ok
10 Correct 40 ms 195156 KB ok
11 Correct 40 ms 195220 KB ok
12 Correct 41 ms 195420 KB ok
13 Correct 40 ms 195164 KB ok
14 Correct 39 ms 195156 KB ok
15 Correct 40 ms 195152 KB ok
16 Correct 40 ms 195376 KB ok
17 Correct 40 ms 197204 KB ok
18 Correct 41 ms 197468 KB ok
19 Correct 40 ms 197208 KB ok
20 Correct 41 ms 197468 KB ok
21 Correct 40 ms 197208 KB ok
22 Correct 40 ms 197208 KB ok
23 Correct 39 ms 197416 KB ok
24 Correct 42 ms 197436 KB ok
25 Correct 40 ms 197208 KB ok
26 Correct 41 ms 197200 KB ok
27 Correct 41 ms 197212 KB ok
28 Correct 41 ms 197212 KB ok
29 Correct 40 ms 197468 KB ok
30 Correct 43 ms 205656 KB ok
31 Correct 42 ms 205652 KB ok
32 Correct 42 ms 205648 KB ok
33 Correct 42 ms 205656 KB ok
34 Correct 41 ms 205616 KB ok
35 Correct 43 ms 205660 KB ok
36 Correct 42 ms 205660 KB ok
37 Correct 43 ms 205648 KB ok
38 Correct 43 ms 205656 KB ok
39 Correct 43 ms 205648 KB ok
40 Correct 42 ms 205660 KB ok
41 Execution timed out 4598 ms 205628 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 197204 KB ok
2 Correct 39 ms 195152 KB ok
3 Correct 41 ms 195372 KB ok
4 Correct 41 ms 197212 KB ok
5 Correct 40 ms 197200 KB ok
6 Correct 41 ms 195352 KB ok
7 Correct 42 ms 195152 KB ok
8 Correct 49 ms 230236 KB ok
9 Correct 87 ms 304660 KB ok
10 Correct 679 ms 921748 KB ok
11 Correct 40 ms 195156 KB ok
12 Correct 41 ms 195356 KB ok
13 Correct 40 ms 195316 KB ok
14 Correct 40 ms 195212 KB ok
15 Correct 40 ms 195156 KB ok
16 Correct 40 ms 195220 KB ok
17 Correct 41 ms 195420 KB ok
18 Correct 40 ms 195164 KB ok
19 Correct 39 ms 195156 KB ok
20 Correct 40 ms 195152 KB ok
21 Correct 40 ms 195376 KB ok
22 Correct 40 ms 197204 KB ok
23 Correct 41 ms 197468 KB ok
24 Correct 40 ms 197208 KB ok
25 Correct 41 ms 197468 KB ok
26 Correct 40 ms 197208 KB ok
27 Correct 40 ms 197208 KB ok
28 Correct 39 ms 197416 KB ok
29 Correct 42 ms 197436 KB ok
30 Correct 40 ms 197208 KB ok
31 Correct 41 ms 197200 KB ok
32 Correct 41 ms 197212 KB ok
33 Correct 41 ms 197212 KB ok
34 Correct 40 ms 197468 KB ok
35 Correct 43 ms 205656 KB ok
36 Correct 42 ms 205652 KB ok
37 Correct 42 ms 205648 KB ok
38 Correct 42 ms 205656 KB ok
39 Correct 41 ms 205616 KB ok
40 Correct 43 ms 205660 KB ok
41 Correct 42 ms 205660 KB ok
42 Correct 43 ms 205648 KB ok
43 Correct 43 ms 205656 KB ok
44 Correct 43 ms 205648 KB ok
45 Correct 42 ms 205660 KB ok
46 Execution timed out 4598 ms 205628 KB Time limit exceeded
47 Halted 0 ms 0 KB -