Submission #1020610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020610		pavement	Soccer Stadium (IOI23_soccer)	C++17	24 / 100	1820 ms	369864 KiB

soccer

#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
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30