oj.uz

Submission #1020610

# Submission time Handle Problem Language Result Execution time Memory
1020610 2024-07-12T07:33:51 Z pavement Soccer Stadium (IOI23_soccer) C++17
24 / 100
 1820 ms 369864 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;

int clr[2005][2005], clu[2005][2005], cld[2005][2005];
ii clrp[2005][2005], clrs[2005][2005], par[4000005];
ll ans, dp[4000005];
vector<int> glob;
set<iii> ft[2005][2005];

vector<iiii> get_maximal_rects(const int &N, const vector<vector<int> > &F) {
	vector<iiii> cur_rects;
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= 0; j--) {
			if (F[i][j] == 1) {
				clr[i][j] = j;
			} else if (j + 1 < N) {
				clr[i][j] = clr[i][j + 1];
			} else {
				clr[i][j] = N;
			}
			if (F[i][j] == 1) {
				clu[i][j] = i;
			} else if (i > 0) {
				clu[i][j] = clu[i - 1][j];
			} else {
				clu[i][j] = -1;
			}
			if (F[i][j] == 1) {
				clrp[i][j] = mp(N, N);
			} else if (i > 0) {
				clrp[i][j] = min(clrp[i - 1][j], mp(clr[i][j], i));
			} else {
				clrp[i][j] = mp(clr[i][j], i);
			}
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			if (F[i][j] == 1) {
				cld[i][j] = i;
			} else if (i + 1 < N) {
				cld[i][j] = cld[i + 1][j];
			} else {
				cld[i][j] = N;
			}
			if (F[i][j] == 1) {
				clrs[i][j] = mp(N, N);
			} else if (i + 1 < N) {
				clrs[i][j] = min(clrs[i + 1][j], mp(clr[i][j], i));
			} else {
				clrs[i][j] = mp(clr[i][j], i);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j] == 1 || (j != 0 && F[i][j - 1] == 0)) {
				continue;
			}
			int l1 = clu[i][j] + 1;
			int r1 = cld[i][j] - 1;
			int nj = j;
			while (l1 <= r1) {
				if (F[l1][nj] == 1 || cld[l1][nj] <= r1) {
					break;
				}
				int b1, g1;
				if (clu[l1][nj] + 1 == l1) {
					tie(b1, g1) = clrp[r1][nj];
				} else {
					tie(b1, g1) = clrs[l1][nj];
				}
				cur_rects.eb(l1, j, r1, b1 - 1);
				// obstacle at (g1, b1)
				if (b1 == N) {
					break;
				}
				if (i < g1) {
					r1 = g1 - 1;
				} else if (i > g1) {
					l1 = g1 + 1;
				} else {
					break;
				}
				nj = b1;
			}
		}
	}
	return cur_rects;
}

vector<vector<int> > rotate(const int &N, const vector<vector<int> > &F) {
	vector<vector<int> > G(N, vector<int>(N, 0));
	for (int col = N - 1; col >= 0; col--) {
		for (int row = 0; row < N; row++) {
			G[row][col] = F[N - col - 1][row];
		}
	}
	return G;
}

ii unpack(const int &N, const int &x) {
	int r = x / N, c = x % N;
	return mp(r, c);
}

int ls(int x) {
	return x & -x;
}

void ft_upd(const int &N, int cl, int cr, int rl, int rr, int idx) {
	for (cl++; cl <= N; cl += ls(cl)) {
		for (int tcr = N - cr; tcr <= N; tcr += ls(tcr)) {
			ft[cl][tcr].emplace(rl, rr, idx);
		}
	}
}

void ft_qry(const int &N, int cl, int cr, int rl, int rr) {
	for (cl++; cl; cl -= ls(cl)) {
		for (int tcr = N - cr; tcr; tcr -= ls(tcr)) {
			vector<set<iii>::iterator> to_erase;
			for (auto it = ft[cl][tcr].lower_bound(mt(rl, 0, 0)); it != ft[cl][tcr].end() && get<1>(*it) <= rr; it++) {
				glob.pb(get<2>(*it));
				to_erase.pb(it);
			}
			for (auto it : to_erase) {
				ft[cl][tcr].erase(it);
			}
		}
	}
}

int biggest_stadium(int N, vector<vector<int> > F) {
	vector<iiii> all_rects;
	vector<vector<int> > H(N, vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			H[i][j] = i * N + j;
		}
	}
	for (int rep = 0; rep < 2; rep++) {
		auto cur_rects = get_maximal_rects(N, F);
		for (auto [r1, c1, r2, c2] : cur_rects) {
			auto [nr1, nc1] = unpack(N, H[r1][c1]);
			auto [nr2, nc2] = unpack(N, H[r2][c2]);
			all_rects.eb(min(nr1, nr2), min(nc1, nc2), max(nr1, nr2), max(nc1, nc2));
		}
		F = rotate(N, F);
		H = rotate(N, H);
	}
	sort(all_rects.begin(), all_rects.end(), [](const auto &lhs, const auto &rhs) {
		auto [r11, c11, r12, c12] = lhs;
		auto [r21, c21, r22, c22] = rhs;
		return c12 - c11 > c22 - c21;
	});
	all_rects.erase(unique(all_rects.begin(), all_rects.end()), all_rects.end());
	for (int i = 0; i < (int)all_rects.size(); i++) {
		auto [r11, c11, r12, c12] = all_rects[i];
		glob.clear();
		ft_qry(N, c11, c12, r11, r12);
		for (auto j : glob) {
			auto [r21, c21, r22, c22] = all_rects[j];
			dp[i] = max(dp[i], dp[j] + (ll)((c22 - c21 + 1) - (c12 - c11 + 1)) * (r22 - r21 + 1));
		}
		ft_upd(N, c11, c12, r11, r12, i);
		ans = max(ans, dp[i] + (ll)(r12 - r11 + 1) * (c12 - c11 + 1));
	}
	return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 189252 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 189264 KB ok
2 Correct 85 ms 189264 KB ok
3 Correct 85 ms 189264 KB ok
4 Correct 100 ms 189264 KB ok
5 Correct 90 ms 189264 KB ok
6 Correct 84 ms 189096 KB ok
7 Correct 86 ms 191568 KB ok
8 Correct 109 ms 210428 KB ok
9 Correct 458 ms 369864 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 189264 KB ok
2 Correct 85 ms 189264 KB ok
3 Correct 85 ms 189264 KB ok
4 Correct 84 ms 189268 KB ok
5 Correct 88 ms 189152 KB ok
6 Correct 90 ms 189268 KB ok
7 Correct 90 ms 189304 KB ok
8 Correct 95 ms 189264 KB ok
9 Correct 87 ms 189264 KB ok
10 Correct 102 ms 189264 KB ok
11 Correct 84 ms 189264 KB ok
12 Correct 104 ms 189204 KB ok
13 Correct 86 ms 189252 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 189252 KB ok
2 Correct 104 ms 189264 KB ok
3 Correct 85 ms 189264 KB ok
4 Correct 85 ms 189264 KB ok
5 Correct 84 ms 189268 KB ok
6 Correct 88 ms 189152 KB ok
7 Correct 90 ms 189268 KB ok
8 Correct 90 ms 189304 KB ok
9 Correct 95 ms 189264 KB ok
10 Correct 87 ms 189264 KB ok
11 Correct 102 ms 189264 KB ok
12 Correct 84 ms 189264 KB ok
13 Correct 104 ms 189204 KB ok
14 Correct 86 ms 189252 KB ok
15 Correct 91 ms 189180 KB ok
16 Correct 107 ms 189264 KB ok
17 Correct 79 ms 189268 KB ok
18 Correct 96 ms 189268 KB ok
19 Correct 78 ms 189264 KB ok
20 Correct 90 ms 189268 KB ok
21 Correct 86 ms 189268 KB ok
22 Correct 95 ms 189360 KB ok
23 Correct 89 ms 189304 KB ok
24 Partially correct 85 ms 189460 KB partial
25 Correct 91 ms 189188 KB ok
26 Correct 87 ms 189212 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 189252 KB ok
2 Correct 104 ms 189264 KB ok
3 Correct 85 ms 189264 KB ok
4 Correct 85 ms 189264 KB ok
5 Correct 100 ms 189264 KB ok
6 Correct 85 ms 189264 KB ok
7 Correct 84 ms 189268 KB ok
8 Correct 88 ms 189152 KB ok
9 Correct 90 ms 189268 KB ok
10 Correct 90 ms 189304 KB ok
11 Correct 95 ms 189264 KB ok
12 Correct 87 ms 189264 KB ok
13 Correct 102 ms 189264 KB ok
14 Correct 84 ms 189264 KB ok
15 Correct 104 ms 189204 KB ok
16 Correct 86 ms 189252 KB ok
17 Correct 91 ms 189180 KB ok
18 Correct 107 ms 189264 KB ok
19 Correct 79 ms 189268 KB ok
20 Correct 96 ms 189268 KB ok
21 Correct 78 ms 189264 KB ok
22 Correct 90 ms 189268 KB ok
23 Correct 86 ms 189268 KB ok
24 Correct 95 ms 189360 KB ok
25 Correct 89 ms 189304 KB ok
26 Partially correct 85 ms 189460 KB partial
27 Correct 91 ms 189188 KB ok
28 Correct 87 ms 189212 KB ok
29 Correct 84 ms 189228 KB ok
30 Correct 89 ms 190008 KB ok
31 Correct 102 ms 190040 KB ok
32 Correct 108 ms 189936 KB ok
33 Correct 85 ms 189752 KB ok
34 Correct 88 ms 189852 KB ok
35 Correct 88 ms 189880 KB ok
36 Correct 85 ms 189788 KB ok
37 Correct 100 ms 189908 KB ok
38 Correct 83 ms 189820 KB ok
39 Correct 94 ms 189780 KB ok
40 Correct 85 ms 189820 KB ok
41 Correct 86 ms 190044 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 189252 KB ok
2 Correct 104 ms 189264 KB ok
3 Correct 85 ms 189264 KB ok
4 Correct 85 ms 189264 KB ok
5 Correct 100 ms 189264 KB ok
6 Correct 85 ms 189264 KB ok
7 Correct 84 ms 189268 KB ok
8 Correct 88 ms 189152 KB ok
9 Correct 90 ms 189268 KB ok
10 Correct 90 ms 189304 KB ok
11 Correct 95 ms 189264 KB ok
12 Correct 87 ms 189264 KB ok
13 Correct 102 ms 189264 KB ok
14 Correct 84 ms 189264 KB ok
15 Correct 104 ms 189204 KB ok
16 Correct 86 ms 189252 KB ok
17 Correct 91 ms 189180 KB ok
18 Correct 107 ms 189264 KB ok
19 Correct 79 ms 189268 KB ok
20 Correct 96 ms 189268 KB ok
21 Correct 78 ms 189264 KB ok
22 Correct 90 ms 189268 KB ok
23 Correct 86 ms 189268 KB ok
24 Correct 95 ms 189360 KB ok
25 Correct 89 ms 189304 KB ok
26 Partially correct 85 ms 189460 KB partial
27 Correct 91 ms 189188 KB ok
28 Correct 87 ms 189212 KB ok
29 Correct 84 ms 189228 KB ok
30 Correct 89 ms 190008 KB ok
31 Correct 102 ms 190040 KB ok
32 Correct 108 ms 189936 KB ok
33 Correct 85 ms 189752 KB ok
34 Correct 88 ms 189852 KB ok
35 Correct 88 ms 189880 KB ok
36 Correct 85 ms 189788 KB ok
37 Correct 100 ms 189908 KB ok
38 Correct 83 ms 189820 KB ok
39 Correct 94 ms 189780 KB ok
40 Correct 85 ms 189820 KB ok
41 Correct 86 ms 190044 KB ok
42 Partially correct 1207 ms 309776 KB partial
43 Correct 1820 ms 360464 KB ok
44 Partially correct 217 ms 229036 KB partial
45 Partially correct 214 ms 223284 KB partial
46 Partially correct 572 ms 265624 KB partial
47 Correct 135 ms 213072 KB ok
48 Incorrect 110 ms 210512 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 189252 KB ok
2 Correct 104 ms 189264 KB ok
3 Correct 85 ms 189264 KB ok
4 Correct 85 ms 189264 KB ok
5 Correct 100 ms 189264 KB ok
6 Correct 90 ms 189264 KB ok
7 Correct 84 ms 189096 KB ok
8 Correct 86 ms 191568 KB ok
9 Correct 109 ms 210428 KB ok
10 Correct 458 ms 369864 KB ok
11 Correct 85 ms 189264 KB ok
12 Correct 84 ms 189268 KB ok
13 Correct 88 ms 189152 KB ok
14 Correct 90 ms 189268 KB ok
15 Correct 90 ms 189304 KB ok
16 Correct 95 ms 189264 KB ok
17 Correct 87 ms 189264 KB ok
18 Correct 102 ms 189264 KB ok
19 Correct 84 ms 189264 KB ok
20 Correct 104 ms 189204 KB ok
21 Correct 86 ms 189252 KB ok
22 Correct 91 ms 189180 KB ok
23 Correct 107 ms 189264 KB ok
24 Correct 79 ms 189268 KB ok
25 Correct 96 ms 189268 KB ok
26 Correct 78 ms 189264 KB ok
27 Correct 90 ms 189268 KB ok
28 Correct 86 ms 189268 KB ok
29 Correct 95 ms 189360 KB ok
30 Correct 89 ms 189304 KB ok
31 Partially correct 85 ms 189460 KB partial
32 Correct 91 ms 189188 KB ok
33 Correct 87 ms 189212 KB ok
34 Correct 84 ms 189228 KB ok
35 Correct 89 ms 190008 KB ok
36 Correct 102 ms 190040 KB ok
37 Correct 108 ms 189936 KB ok
38 Correct 85 ms 189752 KB ok
39 Correct 88 ms 189852 KB ok
40 Correct 88 ms 189880 KB ok
41 Correct 85 ms 189788 KB ok
42 Correct 100 ms 189908 KB ok
43 Correct 83 ms 189820 KB ok
44 Correct 94 ms 189780 KB ok
45 Correct 85 ms 189820 KB ok
46 Correct 86 ms 190044 KB ok
47 Partially correct 1207 ms 309776 KB partial
48 Correct 1820 ms 360464 KB ok
49 Partially correct 217 ms 229036 KB partial
50 Partially correct 214 ms 223284 KB partial
51 Partially correct 572 ms 265624 KB partial
52 Correct 135 ms 213072 KB ok
53 Incorrect 110 ms 210512 KB wrong
54 Halted 0 ms 0 KB -