oj.uz

Submission #861582

# Submission time Handle Problem Language Result Execution time Memory
861582 2023-10-16T13:54:20 Z Pyqe Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1517772 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;
	
	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

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 42 ms 197204 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 195320 KB ok
2 Correct 44 ms 195276 KB ok
3 Correct 40 ms 197204 KB ok
4 Correct 41 ms 197268 KB ok
5 Correct 40 ms 195324 KB ok
6 Correct 40 ms 195184 KB ok
7 Correct 45 ms 230228 KB ok
8 Correct 83 ms 376400 KB ok
9 Correct 623 ms 929072 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 195320 KB ok
2 Correct 44 ms 195276 KB ok
3 Correct 40 ms 195156 KB ok
4 Correct 40 ms 195196 KB ok
5 Correct 40 ms 195488 KB ok
6 Correct 41 ms 195380 KB ok
7 Correct 40 ms 195156 KB ok
8 Correct 42 ms 195396 KB ok
9 Correct 40 ms 195416 KB ok
10 Correct 40 ms 195164 KB ok
11 Correct 40 ms 195164 KB ok
12 Correct 40 ms 195164 KB ok
13 Correct 40 ms 195272 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197204 KB ok
2 Correct 42 ms 195320 KB ok
3 Correct 44 ms 195276 KB ok
4 Correct 40 ms 195156 KB ok
5 Correct 40 ms 195196 KB ok
6 Correct 40 ms 195488 KB ok
7 Correct 41 ms 195380 KB ok
8 Correct 40 ms 195156 KB ok
9 Correct 42 ms 195396 KB ok
10 Correct 40 ms 195416 KB ok
11 Correct 40 ms 195164 KB ok
12 Correct 40 ms 195164 KB ok
13 Correct 40 ms 195164 KB ok
14 Correct 40 ms 195272 KB ok
15 Correct 41 ms 197364 KB ok
16 Correct 44 ms 197284 KB ok
17 Correct 41 ms 197200 KB ok
18 Correct 44 ms 197204 KB ok
19 Correct 42 ms 197212 KB ok
20 Correct 40 ms 197204 KB ok
21 Correct 41 ms 197212 KB ok
22 Correct 42 ms 197204 KB ok
23 Correct 42 ms 197328 KB ok
24 Correct 41 ms 197204 KB ok
25 Correct 42 ms 197212 KB ok
26 Correct 40 ms 197212 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197204 KB ok
2 Correct 42 ms 195320 KB ok
3 Correct 44 ms 195276 KB ok
4 Correct 40 ms 197204 KB ok
5 Correct 41 ms 197268 KB ok
6 Correct 40 ms 195156 KB ok
7 Correct 40 ms 195196 KB ok
8 Correct 40 ms 195488 KB ok
9 Correct 41 ms 195380 KB ok
10 Correct 40 ms 195156 KB ok
11 Correct 42 ms 195396 KB ok
12 Correct 40 ms 195416 KB ok
13 Correct 40 ms 195164 KB ok
14 Correct 40 ms 195164 KB ok
15 Correct 40 ms 195164 KB ok
16 Correct 40 ms 195272 KB ok
17 Correct 41 ms 197364 KB ok
18 Correct 44 ms 197284 KB ok
19 Correct 41 ms 197200 KB ok
20 Correct 44 ms 197204 KB ok
21 Correct 42 ms 197212 KB ok
22 Correct 40 ms 197204 KB ok
23 Correct 41 ms 197212 KB ok
24 Correct 42 ms 197204 KB ok
25 Correct 42 ms 197328 KB ok
26 Correct 41 ms 197204 KB ok
27 Correct 42 ms 197212 KB ok
28 Correct 40 ms 197212 KB ok
29 Correct 42 ms 197200 KB ok
30 Correct 46 ms 205556 KB ok
31 Correct 44 ms 205656 KB ok
32 Correct 41 ms 205648 KB ok
33 Correct 42 ms 205648 KB ok
34 Correct 42 ms 205600 KB ok
35 Correct 42 ms 205652 KB ok
36 Correct 42 ms 205660 KB ok
37 Correct 44 ms 205648 KB ok
38 Correct 41 ms 205652 KB ok
39 Correct 41 ms 205652 KB ok
40 Correct 41 ms 205648 KB ok
41 Correct 42 ms 205516 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197204 KB ok
2 Correct 42 ms 195320 KB ok
3 Correct 44 ms 195276 KB ok
4 Correct 40 ms 197204 KB ok
5 Correct 41 ms 197268 KB ok
6 Correct 40 ms 195156 KB ok
7 Correct 40 ms 195196 KB ok
8 Correct 40 ms 195488 KB ok
9 Correct 41 ms 195380 KB ok
10 Correct 40 ms 195156 KB ok
11 Correct 42 ms 195396 KB ok
12 Correct 40 ms 195416 KB ok
13 Correct 40 ms 195164 KB ok
14 Correct 40 ms 195164 KB ok
15 Correct 40 ms 195164 KB ok
16 Correct 40 ms 195272 KB ok
17 Correct 41 ms 197364 KB ok
18 Correct 44 ms 197284 KB ok
19 Correct 41 ms 197200 KB ok
20 Correct 44 ms 197204 KB ok
21 Correct 42 ms 197212 KB ok
22 Correct 40 ms 197204 KB ok
23 Correct 41 ms 197212 KB ok
24 Correct 42 ms 197204 KB ok
25 Correct 42 ms 197328 KB ok
26 Correct 41 ms 197204 KB ok
27 Correct 42 ms 197212 KB ok
28 Correct 40 ms 197212 KB ok
29 Correct 42 ms 197200 KB ok
30 Correct 46 ms 205556 KB ok
31 Correct 44 ms 205656 KB ok
32 Correct 41 ms 205648 KB ok
33 Correct 42 ms 205648 KB ok
34 Correct 42 ms 205600 KB ok
35 Correct 42 ms 205652 KB ok
36 Correct 42 ms 205660 KB ok
37 Correct 44 ms 205648 KB ok
38 Correct 41 ms 205652 KB ok
39 Correct 41 ms 205652 KB ok
40 Correct 41 ms 205648 KB ok
41 Correct 42 ms 205516 KB ok
42 Correct 353 ms 416176 KB ok
43 Correct 279 ms 406596 KB ok
44 Correct 456 ms 426884 KB ok
45 Correct 420 ms 423488 KB ok
46 Correct 404 ms 424136 KB ok
47 Correct 94 ms 377936 KB ok
48 Correct 132 ms 384848 KB ok
49 Correct 122 ms 384000 KB ok
50 Correct 178 ms 405936 KB ok
51 Correct 205 ms 398516 KB ok
52 Correct 101 ms 380240 KB ok
53 Correct 87 ms 377428 KB ok
54 Correct 97 ms 379464 KB ok
55 Correct 111 ms 382292 KB ok
56 Correct 97 ms 378192 KB ok
57 Correct 175 ms 396688 KB ok
58 Correct 206 ms 397848 KB ok
59 Correct 214 ms 398824 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197204 KB ok
2 Correct 42 ms 195320 KB ok
3 Correct 44 ms 195276 KB ok
4 Correct 40 ms 197204 KB ok
5 Correct 41 ms 197268 KB ok
6 Correct 40 ms 195324 KB ok
7 Correct 40 ms 195184 KB ok
8 Correct 45 ms 230228 KB ok
9 Correct 83 ms 376400 KB ok
10 Correct 623 ms 929072 KB ok
11 Correct 40 ms 195156 KB ok
12 Correct 40 ms 195196 KB ok
13 Correct 40 ms 195488 KB ok
14 Correct 41 ms 195380 KB ok
15 Correct 40 ms 195156 KB ok
16 Correct 42 ms 195396 KB ok
17 Correct 40 ms 195416 KB ok
18 Correct 40 ms 195164 KB ok
19 Correct 40 ms 195164 KB ok
20 Correct 40 ms 195164 KB ok
21 Correct 40 ms 195272 KB ok
22 Correct 41 ms 197364 KB ok
23 Correct 44 ms 197284 KB ok
24 Correct 41 ms 197200 KB ok
25 Correct 44 ms 197204 KB ok
26 Correct 42 ms 197212 KB ok
27 Correct 40 ms 197204 KB ok
28 Correct 41 ms 197212 KB ok
29 Correct 42 ms 197204 KB ok
30 Correct 42 ms 197328 KB ok
31 Correct 41 ms 197204 KB ok
32 Correct 42 ms 197212 KB ok
33 Correct 40 ms 197212 KB ok
34 Correct 42 ms 197200 KB ok
35 Correct 46 ms 205556 KB ok
36 Correct 44 ms 205656 KB ok
37 Correct 41 ms 205648 KB ok
38 Correct 42 ms 205648 KB ok
39 Correct 42 ms 205600 KB ok
40 Correct 42 ms 205652 KB ok
41 Correct 42 ms 205660 KB ok
42 Correct 44 ms 205648 KB ok
43 Correct 41 ms 205652 KB ok
44 Correct 41 ms 205652 KB ok
45 Correct 41 ms 205648 KB ok
46 Correct 42 ms 205516 KB ok
47 Correct 353 ms 416176 KB ok
48 Correct 279 ms 406596 KB ok
49 Correct 456 ms 426884 KB ok
50 Correct 420 ms 423488 KB ok
51 Correct 404 ms 424136 KB ok
52 Correct 94 ms 377936 KB ok
53 Correct 132 ms 384848 KB ok
54 Correct 122 ms 384000 KB ok
55 Correct 178 ms 405936 KB ok
56 Correct 205 ms 398516 KB ok
57 Correct 101 ms 380240 KB ok
58 Correct 87 ms 377428 KB ok
59 Correct 97 ms 379464 KB ok
60 Correct 111 ms 382292 KB ok
61 Correct 97 ms 378192 KB ok
62 Correct 175 ms 396688 KB ok
63 Correct 206 ms 397848 KB ok
64 Correct 214 ms 398824 KB ok
65 Execution timed out 4636 ms 1517772 KB Time limit exceeded
66 Halted 0 ms 0 KB -