oj.uz

Submission #895432

# Submission time Handle Problem Language Result Execution time Memory
895432 2023-12-30T00:06:04 Z omeganot Soccer Stadium (IOI23_soccer) C++17
100 / 100
 3079 ms 950384 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;

const int MAX = 2001;
const int LOG = 11;
int lg[MAX];

struct SparseTable {
	int n;
	vector<vector<int>> sparse;
	SparseTable(int n) {
		this->n = n;
		sparse.assign(n, vector<int>(LOG));
	}
	void build(vector<int>& a) {
		for(int i = 0; i < n; i++) {
			sparse[i][0] = a[i];
		}
		for(int i = 1; i < LOG; i++) {
			for(int j = 0; j + (1 << i) - 1 < n; j++) {
				sparse[j][i] = max(sparse[j][i - 1], sparse[j + (1 << (i - 1))][i - 1]);
			}
		}
	}
	int query(int l, int r) {
		int k = lg[r - l + 1];
		return max(sparse[l][k], sparse[r - (1 << k) + 1][k]);
	}
};

int biggest_stadium(int N, vector<vector<int>> F) {
	lg[1] = 0;
	for(int i = 2; i < MAX; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	vector<vector<int>> treeUp(N, vector<int>(N, -1));
	vector<vector<int>> treeDown(N, vector<int>(N, N));
	vector<SparseTable> sUp(N, SparseTable(N));
	vector<SparseTable> sDown(N, SparseTable(N));
	vector<set<int>> treeRows(N);
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			if(i) {
				treeUp[i][j] = treeUp[i - 1][j];
			}
			if(F[i][j]) {
				treeUp[i][j] = i;
				treeRows[i].insert(j);
			}
		}
	}
	for(int i = N - 1; i >= 0; i--) {
		for(int j = 0; j < N; j++) {
			if(i + 1 < N) {
				treeDown[i][j] = treeDown[i + 1][j];
			}
			if(F[i][j]) {
				treeDown[i][j] = i;
			}
		}
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			treeDown[i][j] *= -1;
		}
		sUp[i].build(treeUp[i]);
		sDown[i].build(treeDown[i]);
	} 
	vector<map<array<int, 4>, int>> width(N);
	array<int, 4> v = {0, 0, 0, 0};
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			int k = j;
			while(k < N && !F[i][k]) {
				k++;
			}
			if(!F[i][j]) {
				int wid = k - j - 1;
				int x1; int y1; int x2; int y2;
				y1 = j; y2 = k - 1;
				x1 = sUp[i].query(y1, y2) + 1;
				x2 = -sDown[i].query(y1, y2) - 1;
				width[wid][{x1, y1, x2, y2}] = (y2 - y1 + 1) * (x2 - x1 + 1);
			}
			j = k; 
		}
	}
	int ans = 0;
	for(int i = N - 1; i >= 0; i--) {
		for(pair<array<int, 4>, int> j : width[i]) {
			ans = max(ans, j.second);
			int x1 = j.first[0]; int y1 = j.first[1]; int x2 = j.first[2]; int y2 = j.first[3];
			if(x1) {
				vector<int> pts(1, y1 - 1);
				set<int>::iterator it = treeRows[x1 - 1].lower_bound(y1);
				while(it != treeRows[x1 - 1].end() && *it <= y2) {
					pts.push_back(*it);
					++it;
				}
				pts.push_back(y2 + 1);
				for(int k = 0; k + 1 < pts.size(); k++) {
					if(pts[k + 1] > pts[k] + 1) {
						int nx1; int ny1; int nx2; int ny2;
						ny1 = pts[k] + 1; ny2 = pts[k + 1] - 1;
						nx1 = sUp[x1 - 1].query(ny1, ny2) + 1;
						if(x2 + 1 < N) {
							nx2 = -sDown[x2 + 1].query(ny1, ny2) - 1;
						} else {
							nx2 = x2;
						}
						int wid = ny2 - ny1;
						int addArea = (ny2 - ny1 + 1) * (nx2 - nx1 + 1) - (ny2 - ny1 + 1) * (x2 - x1 + 1);
						width[wid][{nx1, ny1, nx2, ny2}] = max(width[wid][{nx1, ny1, nx2, ny2}], j.second + addArea);
					}  
				}
			}
			if(x2 + 1 < N) {
				vector<int> pts(1, y1 - 1);
				set<int>::iterator it = treeRows[x2 + 1].lower_bound(y1);
				while(it != treeRows[x2 + 1].end() && *it <= y2) {
					pts.push_back(*it);
					++it;
				}
				pts.push_back(y2 + 1);
				for(int k = 0; k + 1 < pts.size(); k++) {
					if(pts[k + 1] > pts[k] + 1) {
						int nx1; int ny1; int nx2; int ny2;
						ny1 = pts[k] + 1; ny2 = pts[k + 1] - 1;
						if(x1) {
							nx1 = sUp[x1 - 1].query(ny1, ny2) + 1;
						} else {
							nx1 = x1;
						}
						nx2 = -sDown[x2 + 1].query(ny1, ny2) - 1;
						int wid = ny2 - ny1;
						int addArea = (ny2 - ny1 + 1) * (nx2 - nx1 + 1) - (ny2 - ny1 + 1) * (x2 - x1 + 1);
						width[wid][{nx1, ny1, nx2, ny2}] = max(width[wid][{nx1, ny1, nx2, ny2}], j.second + addArea);
					}
				}
			}
		}
	} 
	return ans;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int k = 0; k + 1 < pts.size(); k++) {
      |                    ~~~~~~^~~~~~~~~~~~
soccer.cpp:130:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int k = 0; k + 1 < pts.size(); k++) {
      |                    ~~~~~~^~~~~~~~~~~~
soccer.cpp:75:16: warning: unused variable 'v' [-Wunused-variable]
   75 |  array<int, 4> v = {0, 0, 0, 0};
      |                ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 2 ms 2140 KB ok
8 Correct 75 ms 47828 KB ok
9 Correct 974 ms 760216 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 412 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 436 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 412 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 436 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 440 KB ok
19 Correct 1 ms 344 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 1 ms 344 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 412 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 436 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 440 KB ok
21 Correct 1 ms 344 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 1 ms 344 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 600 KB ok
31 Correct 1 ms 600 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 1 ms 600 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 600 KB ok
39 Correct 1 ms 600 KB ok
40 Correct 1 ms 604 KB ok
41 Correct 1 ms 612 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 412 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 436 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 440 KB ok
21 Correct 1 ms 344 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 1 ms 344 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 600 KB ok
31 Correct 1 ms 600 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 1 ms 600 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 600 KB ok
39 Correct 1 ms 600 KB ok
40 Correct 1 ms 604 KB ok
41 Correct 1 ms 612 KB ok
42 Correct 138 ms 52300 KB ok
43 Correct 151 ms 54280 KB ok
44 Correct 79 ms 48980 KB ok
45 Correct 71 ms 48468 KB ok
46 Correct 121 ms 50588 KB ok
47 Correct 60 ms 47964 KB ok
48 Correct 73 ms 53844 KB ok
49 Correct 72 ms 53268 KB ok
50 Correct 86 ms 51024 KB ok
51 Correct 78 ms 50520 KB ok
52 Correct 85 ms 58196 KB ok
53 Correct 86 ms 58960 KB ok
54 Correct 81 ms 58192 KB ok
55 Correct 81 ms 57184 KB ok
56 Correct 76 ms 54992 KB ok
57 Correct 89 ms 52048 KB ok
58 Correct 100 ms 52408 KB ok
59 Correct 97 ms 52952 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 2 ms 2140 KB ok
9 Correct 75 ms 47828 KB ok
10 Correct 974 ms 760216 KB ok
11 Correct 1 ms 412 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 436 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 440 KB ok
26 Correct 1 ms 344 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 344 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 600 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 604 KB ok
39 Correct 1 ms 604 KB ok
40 Correct 1 ms 600 KB ok
41 Correct 1 ms 600 KB ok
42 Correct 1 ms 604 KB ok
43 Correct 1 ms 600 KB ok
44 Correct 1 ms 600 KB ok
45 Correct 1 ms 604 KB ok
46 Correct 1 ms 612 KB ok
47 Correct 138 ms 52300 KB ok
48 Correct 151 ms 54280 KB ok
49 Correct 79 ms 48980 KB ok
50 Correct 71 ms 48468 KB ok
51 Correct 121 ms 50588 KB ok
52 Correct 60 ms 47964 KB ok
53 Correct 73 ms 53844 KB ok
54 Correct 72 ms 53268 KB ok
55 Correct 86 ms 51024 KB ok
56 Correct 78 ms 50520 KB ok
57 Correct 85 ms 58196 KB ok
58 Correct 86 ms 58960 KB ok
59 Correct 81 ms 58192 KB ok
60 Correct 81 ms 57184 KB ok
61 Correct 76 ms 54992 KB ok
62 Correct 89 ms 52048 KB ok
63 Correct 100 ms 52408 KB ok
64 Correct 97 ms 52952 KB ok
65 Correct 3079 ms 829748 KB ok
66 Correct 2077 ms 938980 KB ok
67 Correct 1635 ms 950384 KB ok
68 Correct 1000 ms 763040 KB ok
69 Correct 1491 ms 776296 KB ok
70 Correct 2053 ms 788428 KB ok
71 Correct 1154 ms 761808 KB ok
72 Correct 913 ms 760404 KB ok
73 Correct 1120 ms 854236 KB ok
74 Correct 1130 ms 852228 KB ok
75 Correct 1146 ms 852696 KB ok
76 Correct 1435 ms 807716 KB ok
77 Correct 1419 ms 807532 KB ok
78 Correct 1121 ms 785248 KB ok
79 Correct 1522 ms 942640 KB ok
80 Correct 1492 ms 940892 KB ok
81 Correct 1452 ms 930272 KB ok
82 Correct 1621 ms 907292 KB ok
83 Correct 1908 ms 929764 KB ok
84 Correct 1285 ms 931124 KB ok
85 Correct 1298 ms 937616 KB ok
86 Correct 1274 ms 923028 KB ok
87 Correct 1284 ms 921340 KB ok
88 Correct 1184 ms 872784 KB ok
89 Correct 956 ms 777880 KB ok
90 Correct 1063 ms 821840 KB ok
91 Correct 983 ms 790420 KB ok
92 Correct 1662 ms 937548 KB ok
93 Correct 1672 ms 941384 KB ok
94 Correct 1473 ms 938200 KB ok
95 Correct 1401 ms 934664 KB ok
96 Correct 1366 ms 933784 KB ok
97 Correct 1389 ms 933536 KB ok
98 Correct 1321 ms 940616 KB ok
99 Correct 2009 ms 837872 KB ok
100 Correct 1521 ms 823616 KB ok
101 Correct 1403 ms 817360 KB ok
102 Correct 1417 ms 823364 KB ok
103 Correct 1650 ms 833884 KB ok
104 Correct 1575 ms 838008 KB ok
105 Correct 1588 ms 840948 KB ok
106 Correct 1713 ms 844060 KB ok
107 Correct 1708 ms 843160 KB ok
108 Correct 1133 ms 791908 KB ok
109 Correct 1125 ms 790608 KB ok