oj.uz

Submission #861588

# Submission time Handle Problem Language Result Execution time Memory
861588 2023-10-16T14:07:27 Z Pyqe Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1268676 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];
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)
{
	return lower_bound(ky+1,ky+nn+1,mp(mp(lb,rb),mp(lb2,rb2)))-ky;
}

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 void dnc(int xx,int x,int lb,int rb)
{
	if(lb<=rb)
	{
		int u,k,l,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)
		{
			nn++;
			ky[nn]={{clb,crb},{lb,rb}};
		}
		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;
			dnc(xx,x,k,e-1);
		}
		dnc(xx,x,k,l);
	}
}

inline int dnc2(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=dnc2(xx,x,k,e-1);
			if(p!=-1&&p2!=-1)
			{
				ae(p,p2);
			}
		}
		p2=dnc2(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);
		}
	}
	sort(ky+1,ky+nn+1);
	for(ii=0;ii<2;ii++)
	{
		u=!ii*2-1;
		for(i=1+(n-1)*ii;i&&i<=n;i+=u)
		{
			dnc2(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: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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197200 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 195164 KB ok
2 Correct 40 ms 195152 KB ok
3 Correct 40 ms 197204 KB ok
4 Correct 42 ms 197280 KB ok
5 Correct 41 ms 195152 KB ok
6 Correct 41 ms 195164 KB ok
7 Correct 48 ms 230348 KB ok
8 Correct 91 ms 376244 KB ok
9 Correct 689 ms 930288 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 195164 KB ok
2 Correct 40 ms 195152 KB ok
3 Correct 40 ms 195152 KB ok
4 Correct 40 ms 195160 KB ok
5 Correct 41 ms 195160 KB ok
6 Correct 40 ms 195320 KB ok
7 Correct 41 ms 195320 KB ok
8 Correct 41 ms 195284 KB ok
9 Correct 42 ms 195152 KB ok
10 Correct 40 ms 195160 KB ok
11 Correct 40 ms 195336 KB ok
12 Correct 41 ms 195164 KB ok
13 Correct 39 ms 195156 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197200 KB ok
2 Correct 41 ms 195164 KB ok
3 Correct 40 ms 195152 KB ok
4 Correct 40 ms 195152 KB ok
5 Correct 40 ms 195160 KB ok
6 Correct 41 ms 195160 KB ok
7 Correct 40 ms 195320 KB ok
8 Correct 41 ms 195320 KB ok
9 Correct 41 ms 195284 KB ok
10 Correct 42 ms 195152 KB ok
11 Correct 40 ms 195160 KB ok
12 Correct 40 ms 195336 KB ok
13 Correct 41 ms 195164 KB ok
14 Correct 39 ms 195156 KB ok
15 Correct 41 ms 197396 KB ok
16 Correct 41 ms 197584 KB ok
17 Correct 41 ms 197464 KB ok
18 Correct 40 ms 197200 KB ok
19 Correct 43 ms 197204 KB ok
20 Correct 41 ms 197468 KB ok
21 Correct 41 ms 197316 KB ok
22 Correct 40 ms 197464 KB ok
23 Correct 40 ms 197372 KB ok
24 Correct 41 ms 197204 KB ok
25 Correct 40 ms 197204 KB ok
26 Correct 40 ms 197200 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197200 KB ok
2 Correct 41 ms 195164 KB ok
3 Correct 40 ms 195152 KB ok
4 Correct 40 ms 197204 KB ok
5 Correct 42 ms 197280 KB ok
6 Correct 40 ms 195152 KB ok
7 Correct 40 ms 195160 KB ok
8 Correct 41 ms 195160 KB ok
9 Correct 40 ms 195320 KB ok
10 Correct 41 ms 195320 KB ok
11 Correct 41 ms 195284 KB ok
12 Correct 42 ms 195152 KB ok
13 Correct 40 ms 195160 KB ok
14 Correct 40 ms 195336 KB ok
15 Correct 41 ms 195164 KB ok
16 Correct 39 ms 195156 KB ok
17 Correct 41 ms 197396 KB ok
18 Correct 41 ms 197584 KB ok
19 Correct 41 ms 197464 KB ok
20 Correct 40 ms 197200 KB ok
21 Correct 43 ms 197204 KB ok
22 Correct 41 ms 197468 KB ok
23 Correct 41 ms 197316 KB ok
24 Correct 40 ms 197464 KB ok
25 Correct 40 ms 197372 KB ok
26 Correct 41 ms 197204 KB ok
27 Correct 40 ms 197204 KB ok
28 Correct 40 ms 197200 KB ok
29 Correct 42 ms 197468 KB ok
30 Correct 42 ms 205660 KB ok
31 Correct 42 ms 205664 KB ok
32 Correct 44 ms 205660 KB ok
33 Correct 43 ms 205652 KB ok
34 Correct 42 ms 205660 KB ok
35 Correct 42 ms 205672 KB ok
36 Correct 42 ms 205664 KB ok
37 Correct 42 ms 205620 KB ok
38 Correct 41 ms 205528 KB ok
39 Correct 42 ms 205520 KB ok
40 Correct 41 ms 205424 KB ok
41 Correct 41 ms 205636 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197200 KB ok
2 Correct 41 ms 195164 KB ok
3 Correct 40 ms 195152 KB ok
4 Correct 40 ms 197204 KB ok
5 Correct 42 ms 197280 KB ok
6 Correct 40 ms 195152 KB ok
7 Correct 40 ms 195160 KB ok
8 Correct 41 ms 195160 KB ok
9 Correct 40 ms 195320 KB ok
10 Correct 41 ms 195320 KB ok
11 Correct 41 ms 195284 KB ok
12 Correct 42 ms 195152 KB ok
13 Correct 40 ms 195160 KB ok
14 Correct 40 ms 195336 KB ok
15 Correct 41 ms 195164 KB ok
16 Correct 39 ms 195156 KB ok
17 Correct 41 ms 197396 KB ok
18 Correct 41 ms 197584 KB ok
19 Correct 41 ms 197464 KB ok
20 Correct 40 ms 197200 KB ok
21 Correct 43 ms 197204 KB ok
22 Correct 41 ms 197468 KB ok
23 Correct 41 ms 197316 KB ok
24 Correct 40 ms 197464 KB ok
25 Correct 40 ms 197372 KB ok
26 Correct 41 ms 197204 KB ok
27 Correct 40 ms 197204 KB ok
28 Correct 40 ms 197200 KB ok
29 Correct 42 ms 197468 KB ok
30 Correct 42 ms 205660 KB ok
31 Correct 42 ms 205664 KB ok
32 Correct 44 ms 205660 KB ok
33 Correct 43 ms 205652 KB ok
34 Correct 42 ms 205660 KB ok
35 Correct 42 ms 205672 KB ok
36 Correct 42 ms 205664 KB ok
37 Correct 42 ms 205620 KB ok
38 Correct 41 ms 205528 KB ok
39 Correct 42 ms 205520 KB ok
40 Correct 41 ms 205424 KB ok
41 Correct 41 ms 205636 KB ok
42 Correct 285 ms 397364 KB ok
43 Correct 236 ms 392340 KB ok
44 Correct 335 ms 400724 KB ok
45 Correct 311 ms 399960 KB ok
46 Correct 319 ms 399696 KB ok
47 Correct 97 ms 377060 KB ok
48 Correct 117 ms 379280 KB ok
49 Correct 116 ms 378912 KB ok
50 Correct 162 ms 390216 KB ok
51 Correct 177 ms 385656 KB ok
52 Correct 100 ms 377812 KB ok
53 Correct 91 ms 376644 KB ok
54 Correct 98 ms 377428 KB ok
55 Correct 107 ms 378564 KB ok
56 Correct 91 ms 376880 KB ok
57 Correct 164 ms 387412 KB ok
58 Correct 178 ms 389824 KB ok
59 Correct 182 ms 390472 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 197200 KB ok
2 Correct 41 ms 195164 KB ok
3 Correct 40 ms 195152 KB ok
4 Correct 40 ms 197204 KB ok
5 Correct 42 ms 197280 KB ok
6 Correct 41 ms 195152 KB ok
7 Correct 41 ms 195164 KB ok
8 Correct 48 ms 230348 KB ok
9 Correct 91 ms 376244 KB ok
10 Correct 689 ms 930288 KB ok
11 Correct 40 ms 195152 KB ok
12 Correct 40 ms 195160 KB ok
13 Correct 41 ms 195160 KB ok
14 Correct 40 ms 195320 KB ok
15 Correct 41 ms 195320 KB ok
16 Correct 41 ms 195284 KB ok
17 Correct 42 ms 195152 KB ok
18 Correct 40 ms 195160 KB ok
19 Correct 40 ms 195336 KB ok
20 Correct 41 ms 195164 KB ok
21 Correct 39 ms 195156 KB ok
22 Correct 41 ms 197396 KB ok
23 Correct 41 ms 197584 KB ok
24 Correct 41 ms 197464 KB ok
25 Correct 40 ms 197200 KB ok
26 Correct 43 ms 197204 KB ok
27 Correct 41 ms 197468 KB ok
28 Correct 41 ms 197316 KB ok
29 Correct 40 ms 197464 KB ok
30 Correct 40 ms 197372 KB ok
31 Correct 41 ms 197204 KB ok
32 Correct 40 ms 197204 KB ok
33 Correct 40 ms 197200 KB ok
34 Correct 42 ms 197468 KB ok
35 Correct 42 ms 205660 KB ok
36 Correct 42 ms 205664 KB ok
37 Correct 44 ms 205660 KB ok
38 Correct 43 ms 205652 KB ok
39 Correct 42 ms 205660 KB ok
40 Correct 42 ms 205672 KB ok
41 Correct 42 ms 205664 KB ok
42 Correct 42 ms 205620 KB ok
43 Correct 41 ms 205528 KB ok
44 Correct 42 ms 205520 KB ok
45 Correct 41 ms 205424 KB ok
46 Correct 41 ms 205636 KB ok
47 Correct 285 ms 397364 KB ok
48 Correct 236 ms 392340 KB ok
49 Correct 335 ms 400724 KB ok
50 Correct 311 ms 399960 KB ok
51 Correct 319 ms 399696 KB ok
52 Correct 97 ms 377060 KB ok
53 Correct 117 ms 379280 KB ok
54 Correct 116 ms 378912 KB ok
55 Correct 162 ms 390216 KB ok
56 Correct 177 ms 385656 KB ok
57 Correct 100 ms 377812 KB ok
58 Correct 91 ms 376644 KB ok
59 Correct 98 ms 377428 KB ok
60 Correct 107 ms 378564 KB ok
61 Correct 91 ms 376880 KB ok
62 Correct 164 ms 387412 KB ok
63 Correct 178 ms 389824 KB ok
64 Correct 182 ms 390472 KB ok
65 Correct 4313 ms 1246172 KB ok
66 Correct 1232 ms 1006920 KB ok
67 Correct 809 ms 961768 KB ok
68 Execution timed out 4585 ms 1268676 KB Time limit exceeded
69 Halted 0 ms 0 KB -