oj.uz

Submission #861608

# Submission time Handle Problem Language Result Execution time Memory
861608 2023-10-16T14:49:25 Z Pyqe Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2760 ms 1842060 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(ky[i].fr.fr&&!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 386132 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 386000 KB ok
2 Correct 80 ms 386080 KB ok
3 Correct 79 ms 388208 KB ok
4 Correct 81 ms 390264 KB ok
5 Correct 79 ms 386128 KB ok
6 Correct 79 ms 386128 KB ok
7 Correct 85 ms 421200 KB ok
8 Correct 128 ms 575764 KB ok
9 Correct 624 ms 1310548 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 386000 KB ok
2 Correct 80 ms 386080 KB ok
3 Correct 80 ms 386128 KB ok
4 Correct 78 ms 386156 KB ok
5 Correct 80 ms 386132 KB ok
6 Correct 78 ms 386136 KB ok
7 Correct 80 ms 386128 KB ok
8 Correct 79 ms 386128 KB ok
9 Correct 79 ms 386072 KB ok
10 Correct 80 ms 386128 KB ok
11 Correct 86 ms 385992 KB ok
12 Correct 80 ms 386132 KB ok
13 Correct 80 ms 386128 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386132 KB ok
2 Correct 80 ms 386000 KB ok
3 Correct 80 ms 386080 KB ok
4 Correct 80 ms 386128 KB ok
5 Correct 78 ms 386156 KB ok
6 Correct 80 ms 386132 KB ok
7 Correct 78 ms 386136 KB ok
8 Correct 80 ms 386128 KB ok
9 Correct 79 ms 386128 KB ok
10 Correct 79 ms 386072 KB ok
11 Correct 80 ms 386128 KB ok
12 Correct 86 ms 385992 KB ok
13 Correct 80 ms 386132 KB ok
14 Correct 80 ms 386128 KB ok
15 Correct 79 ms 388240 KB ok
16 Correct 84 ms 388436 KB ok
17 Correct 81 ms 388104 KB ok
18 Correct 79 ms 388180 KB ok
19 Correct 79 ms 388176 KB ok
20 Correct 83 ms 388176 KB ok
21 Correct 80 ms 388180 KB ok
22 Correct 82 ms 388208 KB ok
23 Correct 81 ms 388176 KB ok
24 Correct 79 ms 388136 KB ok
25 Correct 81 ms 388180 KB ok
26 Correct 79 ms 388176 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386132 KB ok
2 Correct 80 ms 386000 KB ok
3 Correct 80 ms 386080 KB ok
4 Correct 79 ms 388208 KB ok
5 Correct 81 ms 390264 KB ok
6 Correct 80 ms 386128 KB ok
7 Correct 78 ms 386156 KB ok
8 Correct 80 ms 386132 KB ok
9 Correct 78 ms 386136 KB ok
10 Correct 80 ms 386128 KB ok
11 Correct 79 ms 386128 KB ok
12 Correct 79 ms 386072 KB ok
13 Correct 80 ms 386128 KB ok
14 Correct 86 ms 385992 KB ok
15 Correct 80 ms 386132 KB ok
16 Correct 80 ms 386128 KB ok
17 Correct 79 ms 388240 KB ok
18 Correct 84 ms 388436 KB ok
19 Correct 81 ms 388104 KB ok
20 Correct 79 ms 388180 KB ok
21 Correct 79 ms 388176 KB ok
22 Correct 83 ms 388176 KB ok
23 Correct 80 ms 388180 KB ok
24 Correct 82 ms 388208 KB ok
25 Correct 81 ms 388176 KB ok
26 Correct 79 ms 388136 KB ok
27 Correct 81 ms 388180 KB ok
28 Correct 79 ms 388176 KB ok
29 Correct 83 ms 388176 KB ok
30 Correct 82 ms 396372 KB ok
31 Correct 81 ms 396372 KB ok
32 Correct 81 ms 396424 KB ok
33 Correct 80 ms 396352 KB ok
34 Correct 85 ms 396368 KB ok
35 Correct 80 ms 396488 KB ok
36 Correct 84 ms 396372 KB ok
37 Correct 84 ms 396320 KB ok
38 Correct 80 ms 396376 KB ok
39 Correct 80 ms 396372 KB ok
40 Correct 84 ms 396372 KB ok
41 Correct 85 ms 396372 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386132 KB ok
2 Correct 80 ms 386000 KB ok
3 Correct 80 ms 386080 KB ok
4 Correct 79 ms 388208 KB ok
5 Correct 81 ms 390264 KB ok
6 Correct 80 ms 386128 KB ok
7 Correct 78 ms 386156 KB ok
8 Correct 80 ms 386132 KB ok
9 Correct 78 ms 386136 KB ok
10 Correct 80 ms 386128 KB ok
11 Correct 79 ms 386128 KB ok
12 Correct 79 ms 386072 KB ok
13 Correct 80 ms 386128 KB ok
14 Correct 86 ms 385992 KB ok
15 Correct 80 ms 386132 KB ok
16 Correct 80 ms 386128 KB ok
17 Correct 79 ms 388240 KB ok
18 Correct 84 ms 388436 KB ok
19 Correct 81 ms 388104 KB ok
20 Correct 79 ms 388180 KB ok
21 Correct 79 ms 388176 KB ok
22 Correct 83 ms 388176 KB ok
23 Correct 80 ms 388180 KB ok
24 Correct 82 ms 388208 KB ok
25 Correct 81 ms 388176 KB ok
26 Correct 79 ms 388136 KB ok
27 Correct 81 ms 388180 KB ok
28 Correct 79 ms 388176 KB ok
29 Correct 83 ms 388176 KB ok
30 Correct 82 ms 396372 KB ok
31 Correct 81 ms 396372 KB ok
32 Correct 81 ms 396424 KB ok
33 Correct 80 ms 396352 KB ok
34 Correct 85 ms 396368 KB ok
35 Correct 80 ms 396488 KB ok
36 Correct 84 ms 396372 KB ok
37 Correct 84 ms 396320 KB ok
38 Correct 80 ms 396376 KB ok
39 Correct 80 ms 396372 KB ok
40 Correct 84 ms 396372 KB ok
41 Correct 85 ms 396372 KB ok
42 Correct 246 ms 600664 KB ok
43 Correct 206 ms 594940 KB ok
44 Correct 246 ms 607420 KB ok
45 Correct 214 ms 604480 KB ok
46 Correct 238 ms 605324 KB ok
47 Correct 152 ms 577668 KB ok
48 Correct 148 ms 582396 KB ok
49 Correct 143 ms 580868 KB ok
50 Correct 156 ms 594580 KB ok
51 Correct 168 ms 589392 KB ok
52 Correct 134 ms 575312 KB ok
53 Correct 128 ms 570452 KB ok
54 Correct 133 ms 575056 KB ok
55 Correct 140 ms 579920 KB ok
56 Correct 136 ms 575568 KB ok
57 Correct 162 ms 590276 KB ok
58 Correct 186 ms 591188 KB ok
59 Correct 172 ms 592292 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 386132 KB ok
2 Correct 80 ms 386000 KB ok
3 Correct 80 ms 386080 KB ok
4 Correct 79 ms 388208 KB ok
5 Correct 81 ms 390264 KB ok
6 Correct 79 ms 386128 KB ok
7 Correct 79 ms 386128 KB ok
8 Correct 85 ms 421200 KB ok
9 Correct 128 ms 575764 KB ok
10 Correct 624 ms 1310548 KB ok
11 Correct 80 ms 386128 KB ok
12 Correct 78 ms 386156 KB ok
13 Correct 80 ms 386132 KB ok
14 Correct 78 ms 386136 KB ok
15 Correct 80 ms 386128 KB ok
16 Correct 79 ms 386128 KB ok
17 Correct 79 ms 386072 KB ok
18 Correct 80 ms 386128 KB ok
19 Correct 86 ms 385992 KB ok
20 Correct 80 ms 386132 KB ok
21 Correct 80 ms 386128 KB ok
22 Correct 79 ms 388240 KB ok
23 Correct 84 ms 388436 KB ok
24 Correct 81 ms 388104 KB ok
25 Correct 79 ms 388180 KB ok
26 Correct 79 ms 388176 KB ok
27 Correct 83 ms 388176 KB ok
28 Correct 80 ms 388180 KB ok
29 Correct 82 ms 388208 KB ok
30 Correct 81 ms 388176 KB ok
31 Correct 79 ms 388136 KB ok
32 Correct 81 ms 388180 KB ok
33 Correct 79 ms 388176 KB ok
34 Correct 83 ms 388176 KB ok
35 Correct 82 ms 396372 KB ok
36 Correct 81 ms 396372 KB ok
37 Correct 81 ms 396424 KB ok
38 Correct 80 ms 396352 KB ok
39 Correct 85 ms 396368 KB ok
40 Correct 80 ms 396488 KB ok
41 Correct 84 ms 396372 KB ok
42 Correct 84 ms 396320 KB ok
43 Correct 80 ms 396376 KB ok
44 Correct 80 ms 396372 KB ok
45 Correct 84 ms 396372 KB ok
46 Correct 85 ms 396372 KB ok
47 Correct 246 ms 600664 KB ok
48 Correct 206 ms 594940 KB ok
49 Correct 246 ms 607420 KB ok
50 Correct 214 ms 604480 KB ok
51 Correct 238 ms 605324 KB ok
52 Correct 152 ms 577668 KB ok
53 Correct 148 ms 582396 KB ok
54 Correct 143 ms 580868 KB ok
55 Correct 156 ms 594580 KB ok
56 Correct 168 ms 589392 KB ok
57 Correct 134 ms 575312 KB ok
58 Correct 128 ms 570452 KB ok
59 Correct 133 ms 575056 KB ok
60 Correct 140 ms 579920 KB ok
61 Correct 136 ms 575568 KB ok
62 Correct 162 ms 590276 KB ok
63 Correct 186 ms 591188 KB ok
64 Correct 172 ms 592292 KB ok
65 Correct 2481 ms 1703368 KB ok
66 Correct 1032 ms 1363968 KB ok
67 Correct 766 ms 1324908 KB ok
68 Correct 2279 ms 1753232 KB ok
69 Correct 2760 ms 1842060 KB ok
70 Correct 2700 ms 1818096 KB ok
71 Correct 1897 ms 1655668 KB ok
72 Correct 787 ms 1321732 KB ok
73 Correct 975 ms 1388184 KB ok
74 Correct 1012 ms 1388716 KB ok
75 Correct 977 ms 1387872 KB ok
76 Correct 1127 ms 1595896 KB ok
77 Correct 1022 ms 1596100 KB ok
78 Correct 1339 ms 1531096 KB ok
79 Correct 786 ms 1326928 KB ok
80 Correct 768 ms 1326752 KB ok
81 Correct 835 ms 1341984 KB ok
82 Correct 1051 ms 1387292 KB ok
83 Correct 1038 ms 1368860 KB ok
84 Correct 651 ms 1221892 KB ok
85 Correct 625 ms 1190560 KB ok
86 Correct 674 ms 1239120 KB ok
87 Correct 721 ms 1258620 KB ok
88 Correct 670 ms 1260592 KB ok
89 Correct 628 ms 1266784 KB ok
90 Correct 648 ms 1273860 KB ok
91 Correct 714 ms 1292456 KB ok
92 Correct 820 ms 1325392 KB ok
93 Correct 850 ms 1331292 KB ok
94 Correct 770 ms 1316580 KB ok
95 Correct 703 ms 1313280 KB ok
96 Correct 703 ms 1308996 KB ok
97 Correct 689 ms 1301008 KB ok
98 Correct 653 ms 1283560 KB ok
99 Correct 1761 ms 1564580 KB ok
100 Correct 1280 ms 1512532 KB ok
101 Correct 1344 ms 1502532 KB ok
102 Correct 1371 ms 1512904 KB ok
103 Correct 1289 ms 1532320 KB ok
104 Correct 1528 ms 1540676 KB ok
105 Correct 1539 ms 1548104 KB ok
106 Correct 1395 ms 1559836 KB ok
107 Correct 1394 ms 1568036 KB ok
108 Correct 1020 ms 1461776 KB ok
109 Correct 1158 ms 1513296 KB ok