oj.uz

Submission #861599

# Submission time Handle Problem Language Result Execution time Memory
861599 2023-10-16T14:35:42 Z Pyqe Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2724 ms 1842284 KB 
#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(!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 81 ms 386128 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 386132 KB ok
2 Correct 80 ms 386172 KB ok
3 Correct 80 ms 388100 KB ok
4 Correct 80 ms 390228 KB ok
5 Correct 79 ms 386128 KB ok
6 Correct 81 ms 386132 KB ok
7 Correct 85 ms 421228 KB ok
8 Correct 130 ms 575948 KB ok
9 Correct 685 ms 1280732 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 386132 KB ok
2 Correct 80 ms 386172 KB ok
3 Correct 81 ms 386132 KB ok
4 Correct 81 ms 386180 KB ok
5 Correct 79 ms 386104 KB ok
6 Correct 81 ms 386128 KB ok
7 Correct 79 ms 386132 KB ok
8 Correct 80 ms 386212 KB ok
9 Correct 85 ms 386500 KB ok
10 Correct 80 ms 386136 KB ok
11 Correct 79 ms 386144 KB ok
12 Correct 81 ms 386132 KB ok
13 Correct 80 ms 386116 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386128 KB ok
2 Correct 80 ms 386132 KB ok
3 Correct 80 ms 386172 KB ok
4 Correct 81 ms 386132 KB ok
5 Correct 81 ms 386180 KB ok
6 Correct 79 ms 386104 KB ok
7 Correct 81 ms 386128 KB ok
8 Correct 79 ms 386132 KB ok
9 Correct 80 ms 386212 KB ok
10 Correct 85 ms 386500 KB ok
11 Correct 80 ms 386136 KB ok
12 Correct 79 ms 386144 KB ok
13 Correct 81 ms 386132 KB ok
14 Correct 80 ms 386116 KB ok
15 Correct 81 ms 388244 KB ok
16 Correct 79 ms 388176 KB ok
17 Correct 80 ms 388176 KB ok
18 Correct 79 ms 388152 KB ok
19 Correct 80 ms 388136 KB ok
20 Correct 80 ms 388176 KB ok
21 Correct 79 ms 388176 KB ok
22 Correct 80 ms 388136 KB ok
23 Correct 81 ms 388168 KB ok
24 Correct 80 ms 388180 KB ok
25 Correct 79 ms 388176 KB ok
26 Correct 80 ms 388176 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386128 KB ok
2 Correct 80 ms 386132 KB ok
3 Correct 80 ms 386172 KB ok
4 Correct 80 ms 388100 KB ok
5 Correct 80 ms 390228 KB ok
6 Correct 81 ms 386132 KB ok
7 Correct 81 ms 386180 KB ok
8 Correct 79 ms 386104 KB ok
9 Correct 81 ms 386128 KB ok
10 Correct 79 ms 386132 KB ok
11 Correct 80 ms 386212 KB ok
12 Correct 85 ms 386500 KB ok
13 Correct 80 ms 386136 KB ok
14 Correct 79 ms 386144 KB ok
15 Correct 81 ms 386132 KB ok
16 Correct 80 ms 386116 KB ok
17 Correct 81 ms 388244 KB ok
18 Correct 79 ms 388176 KB ok
19 Correct 80 ms 388176 KB ok
20 Correct 79 ms 388152 KB ok
21 Correct 80 ms 388136 KB ok
22 Correct 80 ms 388176 KB ok
23 Correct 79 ms 388176 KB ok
24 Correct 80 ms 388136 KB ok
25 Correct 81 ms 388168 KB ok
26 Correct 80 ms 388180 KB ok
27 Correct 79 ms 388176 KB ok
28 Correct 80 ms 388176 KB ok
29 Correct 79 ms 388228 KB ok
30 Correct 82 ms 396372 KB ok
31 Correct 83 ms 396316 KB ok
32 Correct 82 ms 396440 KB ok
33 Correct 82 ms 396472 KB ok
34 Correct 81 ms 396372 KB ok
35 Correct 82 ms 396452 KB ok
36 Correct 80 ms 396368 KB ok
37 Correct 82 ms 396368 KB ok
38 Correct 82 ms 396352 KB ok
39 Correct 79 ms 396372 KB ok
40 Correct 82 ms 396724 KB ok
41 Correct 80 ms 396388 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386128 KB ok
2 Correct 80 ms 386132 KB ok
3 Correct 80 ms 386172 KB ok
4 Correct 80 ms 388100 KB ok
5 Correct 80 ms 390228 KB ok
6 Correct 81 ms 386132 KB ok
7 Correct 81 ms 386180 KB ok
8 Correct 79 ms 386104 KB ok
9 Correct 81 ms 386128 KB ok
10 Correct 79 ms 386132 KB ok
11 Correct 80 ms 386212 KB ok
12 Correct 85 ms 386500 KB ok
13 Correct 80 ms 386136 KB ok
14 Correct 79 ms 386144 KB ok
15 Correct 81 ms 386132 KB ok
16 Correct 80 ms 386116 KB ok
17 Correct 81 ms 388244 KB ok
18 Correct 79 ms 388176 KB ok
19 Correct 80 ms 388176 KB ok
20 Correct 79 ms 388152 KB ok
21 Correct 80 ms 388136 KB ok
22 Correct 80 ms 388176 KB ok
23 Correct 79 ms 388176 KB ok
24 Correct 80 ms 388136 KB ok
25 Correct 81 ms 388168 KB ok
26 Correct 80 ms 388180 KB ok
27 Correct 79 ms 388176 KB ok
28 Correct 80 ms 388176 KB ok
29 Correct 79 ms 388228 KB ok
30 Correct 82 ms 396372 KB ok
31 Correct 83 ms 396316 KB ok
32 Correct 82 ms 396440 KB ok
33 Correct 82 ms 396472 KB ok
34 Correct 81 ms 396372 KB ok
35 Correct 82 ms 396452 KB ok
36 Correct 80 ms 396368 KB ok
37 Correct 82 ms 396368 KB ok
38 Correct 82 ms 396352 KB ok
39 Correct 79 ms 396372 KB ok
40 Correct 82 ms 396724 KB ok
41 Correct 80 ms 396388 KB ok
42 Correct 231 ms 600740 KB ok
43 Correct 208 ms 594892 KB ok
44 Correct 228 ms 607056 KB ok
45 Correct 215 ms 604624 KB ok
46 Correct 241 ms 605252 KB ok
47 Correct 137 ms 577704 KB ok
48 Correct 148 ms 582460 KB ok
49 Correct 151 ms 581072 KB ok
50 Correct 155 ms 594092 KB ok
51 Correct 168 ms 589316 KB ok
52 Correct 135 ms 575316 KB ok
53 Correct 132 ms 570688 KB ok
54 Correct 135 ms 575184 KB ok
55 Correct 141 ms 580100 KB ok
56 Correct 132 ms 575148 KB ok
57 Correct 161 ms 590160 KB ok
58 Correct 163 ms 591184 KB ok
59 Correct 168 ms 592288 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386128 KB ok
2 Correct 80 ms 386132 KB ok
3 Correct 80 ms 386172 KB ok
4 Correct 80 ms 388100 KB ok
5 Correct 80 ms 390228 KB ok
6 Correct 79 ms 386128 KB ok
7 Correct 81 ms 386132 KB ok
8 Correct 85 ms 421228 KB ok
9 Correct 130 ms 575948 KB ok
10 Correct 685 ms 1280732 KB ok
11 Correct 81 ms 386132 KB ok
12 Correct 81 ms 386180 KB ok
13 Correct 79 ms 386104 KB ok
14 Correct 81 ms 386128 KB ok
15 Correct 79 ms 386132 KB ok
16 Correct 80 ms 386212 KB ok
17 Correct 85 ms 386500 KB ok
18 Correct 80 ms 386136 KB ok
19 Correct 79 ms 386144 KB ok
20 Correct 81 ms 386132 KB ok
21 Correct 80 ms 386116 KB ok
22 Correct 81 ms 388244 KB ok
23 Correct 79 ms 388176 KB ok
24 Correct 80 ms 388176 KB ok
25 Correct 79 ms 388152 KB ok
26 Correct 80 ms 388136 KB ok
27 Correct 80 ms 388176 KB ok
28 Correct 79 ms 388176 KB ok
29 Correct 80 ms 388136 KB ok
30 Correct 81 ms 388168 KB ok
31 Correct 80 ms 388180 KB ok
32 Correct 79 ms 388176 KB ok
33 Correct 80 ms 388176 KB ok
34 Correct 79 ms 388228 KB ok
35 Correct 82 ms 396372 KB ok
36 Correct 83 ms 396316 KB ok
37 Correct 82 ms 396440 KB ok
38 Correct 82 ms 396472 KB ok
39 Correct 81 ms 396372 KB ok
40 Correct 82 ms 396452 KB ok
41 Correct 80 ms 396368 KB ok
42 Correct 82 ms 396368 KB ok
43 Correct 82 ms 396352 KB ok
44 Correct 79 ms 396372 KB ok
45 Correct 82 ms 396724 KB ok
46 Correct 80 ms 396388 KB ok
47 Correct 231 ms 600740 KB ok
48 Correct 208 ms 594892 KB ok
49 Correct 228 ms 607056 KB ok
50 Correct 215 ms 604624 KB ok
51 Correct 241 ms 605252 KB ok
52 Correct 137 ms 577704 KB ok
53 Correct 148 ms 582460 KB ok
54 Correct 151 ms 581072 KB ok
55 Correct 155 ms 594092 KB ok
56 Correct 168 ms 589316 KB ok
57 Correct 135 ms 575316 KB ok
58 Correct 132 ms 570688 KB ok
59 Correct 135 ms 575184 KB ok
60 Correct 141 ms 580100 KB ok
61 Correct 132 ms 575148 KB ok
62 Correct 161 ms 590160 KB ok
63 Correct 163 ms 591184 KB ok
64 Correct 168 ms 592288 KB ok
65 Correct 2662 ms 1703404 KB ok
66 Correct 975 ms 1363796 KB ok
67 Correct 744 ms 1324880 KB ok
68 Correct 2223 ms 1753320 KB ok
69 Correct 2724 ms 1842284 KB ok
70 Correct 2681 ms 1820688 KB ok
71 Correct 1878 ms 1657132 KB ok
72 Correct 773 ms 1321872 KB ok
73 Correct 960 ms 1388720 KB ok
74 Correct 956 ms 1389056 KB ok
75 Correct 968 ms 1388464 KB ok
76 Correct 1094 ms 1595984 KB ok
77 Correct 1045 ms 1596220 KB ok
78 Correct 1367 ms 1531236 KB ok
79 Correct 800 ms 1326836 KB ok
80 Correct 822 ms 1326900 KB ok
81 Correct 870 ms 1341748 KB ok
82 Correct 1065 ms 1387100 KB ok
83 Correct 1049 ms 1368724 KB ok
84 Correct 699 ms 1238872 KB ok
85 Correct 652 ms 1211732 KB ok
86 Correct 711 ms 1253856 KB ok
87 Correct 735 ms 1272144 KB ok
88 Correct 702 ms 1272024 KB ok
89 Correct 663 ms 1267020 KB ok
90 Correct 674 ms 1274452 KB ok
91 Correct 738 ms 1292884 KB ok
92 Correct 833 ms 1325228 KB ok
93 Correct 840 ms 1331536 KB ok
94 Correct 750 ms 1317124 KB ok
95 Correct 731 ms 1313360 KB ok
96 Correct 707 ms 1309192 KB ok
97 Correct 703 ms 1301088 KB ok
98 Correct 670 ms 1283580 KB ok
99 Correct 1683 ms 1565156 KB ok
100 Correct 1233 ms 1512528 KB ok
101 Correct 1325 ms 1502208 KB ok
102 Correct 1359 ms 1513044 KB ok
103 Correct 1290 ms 1532396 KB ok
104 Correct 1472 ms 1541636 KB ok
105 Correct 1544 ms 1548456 KB ok
106 Correct 1398 ms 1559984 KB ok
107 Correct 1379 ms 1568416 KB ok
108 Correct 1022 ms 1461884 KB ok
109 Correct 1160 ms 1513044 KB ok