oj.uz

Submission #861614

# Submission time Handle Problem Language Result Execution time Memory
861614 2023-10-16T14:58:25 Z Pyqe Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2013 ms 1360772 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<int> al[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)
{
	al[x].push_back(y);
}

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=al[x].size(),l,w,clb,crb,lb,rb,lb2,rb2;
	
	vtd[x]=1;
	dp[x]=0;
	for(i=0;i<sz;i++)
	{
		l=fd(al[x][i]);
		clb=ky[x].fr.fr;
		crb=ky[x].fr.sc;
		lb=ky[l].fr.fr;
		rb=ky[l].fr.sc;
		lb2=ky[l].sc.fr;
		rb2=ky[l].sc.sc;
		w=(rb-lb-(crb-clb))*(rb2-lb2+1);
		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,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++)
	{
		if(fd(i)!=i)
		{
			sz=al[i].size();
			for(j=0;j<sz;j++)
			{
				l=al[i][j];
				al[fd(i)].push_back(l);
			}
		}
	}
	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 42 ms 199364 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 197240 KB ok
2 Correct 42 ms 197200 KB ok
3 Correct 40 ms 199512 KB ok
4 Correct 40 ms 199516 KB ok
5 Correct 44 ms 197368 KB ok
6 Correct 40 ms 197468 KB ok
7 Correct 45 ms 232452 KB ok
8 Correct 89 ms 391760 KB ok
9 Correct 610 ms 1127048 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 197240 KB ok
2 Correct 42 ms 197200 KB ok
3 Correct 40 ms 197384 KB ok
4 Correct 40 ms 197200 KB ok
5 Correct 41 ms 197204 KB ok
6 Correct 40 ms 197204 KB ok
7 Correct 40 ms 197212 KB ok
8 Correct 40 ms 197204 KB ok
9 Correct 43 ms 197204 KB ok
10 Correct 42 ms 197200 KB ok
11 Correct 40 ms 197468 KB ok
12 Correct 40 ms 197468 KB ok
13 Correct 41 ms 197468 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 199364 KB ok
2 Correct 41 ms 197240 KB ok
3 Correct 42 ms 197200 KB ok
4 Correct 40 ms 197384 KB ok
5 Correct 40 ms 197200 KB ok
6 Correct 41 ms 197204 KB ok
7 Correct 40 ms 197204 KB ok
8 Correct 40 ms 197212 KB ok
9 Correct 40 ms 197204 KB ok
10 Correct 43 ms 197204 KB ok
11 Correct 42 ms 197200 KB ok
12 Correct 40 ms 197468 KB ok
13 Correct 40 ms 197468 KB ok
14 Correct 41 ms 197468 KB ok
15 Correct 41 ms 199248 KB ok
16 Correct 46 ms 199252 KB ok
17 Correct 40 ms 199248 KB ok
18 Correct 41 ms 199252 KB ok
19 Correct 43 ms 199336 KB ok
20 Correct 41 ms 199252 KB ok
21 Correct 42 ms 199412 KB ok
22 Correct 42 ms 199352 KB ok
23 Correct 42 ms 199448 KB ok
24 Correct 44 ms 199516 KB ok
25 Correct 44 ms 199504 KB ok
26 Correct 42 ms 199504 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 199364 KB ok
2 Correct 41 ms 197240 KB ok
3 Correct 42 ms 197200 KB ok
4 Correct 40 ms 199512 KB ok
5 Correct 40 ms 199516 KB ok
6 Correct 40 ms 197384 KB ok
7 Correct 40 ms 197200 KB ok
8 Correct 41 ms 197204 KB ok
9 Correct 40 ms 197204 KB ok
10 Correct 40 ms 197212 KB ok
11 Correct 40 ms 197204 KB ok
12 Correct 43 ms 197204 KB ok
13 Correct 42 ms 197200 KB ok
14 Correct 40 ms 197468 KB ok
15 Correct 40 ms 197468 KB ok
16 Correct 41 ms 197468 KB ok
17 Correct 41 ms 199248 KB ok
18 Correct 46 ms 199252 KB ok
19 Correct 40 ms 199248 KB ok
20 Correct 41 ms 199252 KB ok
21 Correct 43 ms 199336 KB ok
22 Correct 41 ms 199252 KB ok
23 Correct 42 ms 199412 KB ok
24 Correct 42 ms 199352 KB ok
25 Correct 42 ms 199448 KB ok
26 Correct 44 ms 199516 KB ok
27 Correct 44 ms 199504 KB ok
28 Correct 42 ms 199504 KB ok
29 Correct 43 ms 199248 KB ok
30 Correct 44 ms 207592 KB ok
31 Correct 41 ms 207700 KB ok
32 Correct 42 ms 207696 KB ok
33 Correct 46 ms 207708 KB ok
34 Correct 42 ms 207700 KB ok
35 Correct 44 ms 207700 KB ok
36 Correct 46 ms 207704 KB ok
37 Correct 43 ms 207700 KB ok
38 Correct 43 ms 207640 KB ok
39 Correct 45 ms 207700 KB ok
40 Correct 46 ms 207876 KB ok
41 Correct 44 ms 207652 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 199364 KB ok
2 Correct 41 ms 197240 KB ok
3 Correct 42 ms 197200 KB ok
4 Correct 40 ms 199512 KB ok
5 Correct 40 ms 199516 KB ok
6 Correct 40 ms 197384 KB ok
7 Correct 40 ms 197200 KB ok
8 Correct 41 ms 197204 KB ok
9 Correct 40 ms 197204 KB ok
10 Correct 40 ms 197212 KB ok
11 Correct 40 ms 197204 KB ok
12 Correct 43 ms 197204 KB ok
13 Correct 42 ms 197200 KB ok
14 Correct 40 ms 197468 KB ok
15 Correct 40 ms 197468 KB ok
16 Correct 41 ms 197468 KB ok
17 Correct 41 ms 199248 KB ok
18 Correct 46 ms 199252 KB ok
19 Correct 40 ms 199248 KB ok
20 Correct 41 ms 199252 KB ok
21 Correct 43 ms 199336 KB ok
22 Correct 41 ms 199252 KB ok
23 Correct 42 ms 199412 KB ok
24 Correct 42 ms 199352 KB ok
25 Correct 42 ms 199448 KB ok
26 Correct 44 ms 199516 KB ok
27 Correct 44 ms 199504 KB ok
28 Correct 42 ms 199504 KB ok
29 Correct 43 ms 199248 KB ok
30 Correct 44 ms 207592 KB ok
31 Correct 41 ms 207700 KB ok
32 Correct 42 ms 207696 KB ok
33 Correct 46 ms 207708 KB ok
34 Correct 42 ms 207700 KB ok
35 Correct 44 ms 207700 KB ok
36 Correct 46 ms 207704 KB ok
37 Correct 43 ms 207700 KB ok
38 Correct 43 ms 207640 KB ok
39 Correct 45 ms 207700 KB ok
40 Correct 46 ms 207876 KB ok
41 Correct 44 ms 207652 KB ok
42 Correct 185 ms 403708 KB ok
43 Correct 174 ms 401348 KB ok
44 Correct 158 ms 405332 KB ok
45 Correct 154 ms 404052 KB ok
46 Correct 190 ms 405288 KB ok
47 Correct 114 ms 392532 KB ok
48 Correct 112 ms 394580 KB ok
49 Correct 113 ms 394064 KB ok
50 Correct 110 ms 400508 KB ok
51 Correct 129 ms 398168 KB ok
52 Correct 96 ms 390908 KB ok
53 Correct 93 ms 388020 KB ok
54 Correct 98 ms 390700 KB ok
55 Correct 110 ms 391764 KB ok
56 Correct 96 ms 390200 KB ok
57 Correct 114 ms 399544 KB ok
58 Correct 119 ms 400300 KB ok
59 Correct 121 ms 400880 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 199364 KB ok
2 Correct 41 ms 197240 KB ok
3 Correct 42 ms 197200 KB ok
4 Correct 40 ms 199512 KB ok
5 Correct 40 ms 199516 KB ok
6 Correct 44 ms 197368 KB ok
7 Correct 40 ms 197468 KB ok
8 Correct 45 ms 232452 KB ok
9 Correct 89 ms 391760 KB ok
10 Correct 610 ms 1127048 KB ok
11 Correct 40 ms 197384 KB ok
12 Correct 40 ms 197200 KB ok
13 Correct 41 ms 197204 KB ok
14 Correct 40 ms 197204 KB ok
15 Correct 40 ms 197212 KB ok
16 Correct 40 ms 197204 KB ok
17 Correct 43 ms 197204 KB ok
18 Correct 42 ms 197200 KB ok
19 Correct 40 ms 197468 KB ok
20 Correct 40 ms 197468 KB ok
21 Correct 41 ms 197468 KB ok
22 Correct 41 ms 199248 KB ok
23 Correct 46 ms 199252 KB ok
24 Correct 40 ms 199248 KB ok
25 Correct 41 ms 199252 KB ok
26 Correct 43 ms 199336 KB ok
27 Correct 41 ms 199252 KB ok
28 Correct 42 ms 199412 KB ok
29 Correct 42 ms 199352 KB ok
30 Correct 42 ms 199448 KB ok
31 Correct 44 ms 199516 KB ok
32 Correct 44 ms 199504 KB ok
33 Correct 42 ms 199504 KB ok
34 Correct 43 ms 199248 KB ok
35 Correct 44 ms 207592 KB ok
36 Correct 41 ms 207700 KB ok
37 Correct 42 ms 207696 KB ok
38 Correct 46 ms 207708 KB ok
39 Correct 42 ms 207700 KB ok
40 Correct 44 ms 207700 KB ok
41 Correct 46 ms 207704 KB ok
42 Correct 43 ms 207700 KB ok
43 Correct 43 ms 207640 KB ok
44 Correct 45 ms 207700 KB ok
45 Correct 46 ms 207876 KB ok
46 Correct 44 ms 207652 KB ok
47 Correct 185 ms 403708 KB ok
48 Correct 174 ms 401348 KB ok
49 Correct 158 ms 405332 KB ok
50 Correct 154 ms 404052 KB ok
51 Correct 190 ms 405288 KB ok
52 Correct 114 ms 392532 KB ok
53 Correct 112 ms 394580 KB ok
54 Correct 113 ms 394064 KB ok
55 Correct 110 ms 400508 KB ok
56 Correct 129 ms 398168 KB ok
57 Correct 96 ms 390908 KB ok
58 Correct 93 ms 388020 KB ok
59 Correct 98 ms 390700 KB ok
60 Correct 110 ms 391764 KB ok
61 Correct 96 ms 390200 KB ok
62 Correct 114 ms 399544 KB ok
63 Correct 119 ms 400300 KB ok
64 Correct 121 ms 400880 KB ok
65 Correct 1901 ms 1318040 KB ok
66 Correct 974 ms 1157016 KB ok
67 Correct 804 ms 1134788 KB ok
68 Correct 1627 ms 1313052 KB ok
69 Correct 1970 ms 1360772 KB ok
70 Correct 2013 ms 1356004 KB ok
71 Correct 1378 ms 1269072 KB ok
72 Correct 707 ms 1131108 KB ok
73 Correct 809 ms 1169756 KB ok
74 Correct 807 ms 1170892 KB ok
75 Correct 796 ms 1169832 KB ok
76 Correct 893 ms 1266804 KB ok
77 Correct 907 ms 1267152 KB ok
78 Correct 1147 ms 1236588 KB ok
79 Correct 745 ms 1133472 KB ok
80 Correct 757 ms 1133464 KB ok
81 Correct 789 ms 1141836 KB ok
82 Correct 930 ms 1164464 KB ok
83 Correct 955 ms 1157204 KB ok
84 Correct 622 ms 1036728 KB ok
85 Correct 591 ms 1011556 KB ok
86 Correct 638 ms 1052864 KB ok
87 Correct 649 ms 1064008 KB ok
88 Correct 645 ms 1065620 KB ok
89 Correct 632 ms 1126956 KB ok
90 Correct 630 ms 1127836 KB ok
91 Correct 665 ms 1129372 KB ok
92 Correct 820 ms 1132700 KB ok
93 Correct 811 ms 1135856 KB ok
94 Correct 708 ms 1127824 KB ok
95 Correct 706 ms 1126444 KB ok
96 Correct 659 ms 1126412 KB ok
97 Correct 641 ms 1126400 KB ok
98 Correct 627 ms 1125784 KB ok
99 Correct 1426 ms 1262436 KB ok
100 Correct 1085 ms 1250964 KB ok
101 Correct 1111 ms 1244404 KB ok
102 Correct 1148 ms 1250652 KB ok
103 Correct 1093 ms 1262092 KB ok
104 Correct 1252 ms 1266800 KB ok
105 Correct 1288 ms 1270840 KB ok
106 Correct 1193 ms 1277520 KB ok
107 Correct 1179 ms 1281092 KB ok
108 Correct 859 ms 1196268 KB ok
109 Correct 979 ms 1219548 KB ok