Submission #1288516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288516		kaiboy	Sandcastle 2 (JOI22_ho_t5)	C++20	80 / 100	5094 ms	20196 KiB

Main

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const int     N = 50000;
const int ddi[] = { -1, 1, 0, 0 };
const int ddj[] = { 0, 0, -1, 1 };

int *aa[N], *ss[3][3][N], kk[N + 1];

bool check(int i, int j, int il, int ir, int jl, int jr) {
	for (int h = 0; h < 4; h++) {
		int i0 = i + ddi[h], j0 = j + ddj[h];
		if (il <= i0 && i0 <= ir && jl <= j0 && j0 <= jr) {
			int i_ = -1, j_ = -1;
			for (int h_ = 0; h_ < 4; h_++) {
				int i1 = i0 + ddi[h_], j1 = j0 + ddj[h_];
				if (il <= i1 && i1 <= ir && jl <= j1 && j1 <= jr
						&& aa[i1][j1] < aa[i0][j0] && (i_ == -1 || aa[i_][j_] < aa[i1][j1]))
					i_ = i1, j_ = j1;
			}
			if (i_ == i && j_ == j)
				return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	int n_ = n, m_ = m;
	bool swapped = false;
	if (n < m)
		swap(n, m), swapped = true;
	for (int i = 0; i < n; i++)
		aa[i] = new int[m];
	for (int i = 0; i < n_; i++)
		for (int j = 0; j < m_; j++)
			if (!swapped)
				cin >> aa[i][j];
			else
				cin >> aa[j][i];
	for (int n0 = 0; n0 <= 2; n0++)
		for (int n1 = 0; n1 <= 2; n1++)
			for (int i = n0; i + n1 < n; i++) {
				ss[n0][n1][i] = new int[m];
				for (int j = 0; j < m; j++)
					ss[n0][n1][i][j] = !check(i, j, i - n0, i + n1, 0, m - 1);
				for (int j = 1; j < m; j++)
					ss[n0][n1][i][j] += ss[n0][n1][i][j - 1];
			}
	int ans = 0;
	for (int jl = 0; jl < m; jl++)
		for (int jr = jl; jr < m; jr++) {
			for (int s = 0; s <= n * m; s++)
				kk[s] = 0;
			for (int s = 0, ir = 0; ir < n; ir++) {
				for (int il = max(ir - 2, 0); il <= ir; il++) {
					int k = 0;
					for (int i_ = il; i_ <= ir; i_++)
						if (jr - jl + 1 > 4) {
							for (int j_ = jl; j_ <= jl + 1; j_++)
								k += !check(i_, j_, il, ir, jl, jr);
							int n0 = i_ - il, n1 = ir - i_;
							k += ss[n0][n1][i_][jr - 2] - ss[n0][n1][i_][jl + 1];
							for (int j_ = jr - 1; j_ <= jr; j_++)
								k += !check(i_, j_, il, ir, jl, jr);
						} else
							for (int j_ = jl; j_ <= jr; j_++)
								k += !check(i_, j_, il, ir, jl, jr);
					if (k == 1)
						ans++;
				}
				if (ir >= 3) {
					int p = s;
					for (int i_ = ir - 1; i_ <= ir; i_++)
						if (jr - jl + 1 > 4) {
							for (int j_ = jl; j_ <= jl + 1; j_++)
								p += !check(i_, j_, 0, ir, jl, jr);
							int n0 = min(i_, 2), n1 = ir - i_;
							p += ss[n0][n1][i_][jr - 2] - ss[n0][n1][i_][jl + 1];
							for (int j_ = jr - 1; j_ <= jr; j_++)
								p += !check(i_, j_, 0, ir, jl, jr);
						} else
							for (int j_ = jl; j_ <= jr; j_++)
								p += !check(i_, j_, 0, ir, jl, jr);
					int q = s;
					for (int i_ = ir - 3; i_ <= ir - 2; i_++)
						if (jr - jl + 1 > 4) {
							for (int j_ = jl; j_ <= jl + 1; j_++)
								q -= !check(i_, j_, ir - 3, n - 1, jl, jr);
							int n0 = i_ - (ir - 3);
							q -= ss[n0][2][i_][jr - 2] - ss[n0][2][i_][jl + 1];
							for (int j_ = jr - 1; j_ <= jr; j_++)
								q -= !check(i_, j_, ir - 3, n - 1, jl, jr);
						} else
							for (int j_ = jl; j_ <= jr; j_++)
								q -= !check(i_, j_, ir - 3, n - 1, jl, jr);
					if (q >= -1)
						kk[q + 1]++;
					ans += kk[p];
					if (ir + 1 < n) {
						int i_ = ir - 1;
						if (jr - jl + 1 > 4) {
							for (int j_ = jl; j_ <= jl + 1; j_++)
								s += !check(i_, j_, 0, n - 1, jl, jr);
							s += ss[2][2][i_][jr - 2] - ss[2][2][i_][jl + 1];
							for (int j_ = jr - 1; j_ <= jr; j_++)
								s += !check(i_, j_, 0, n - 1, jl, jr);
						} else
							for (int j_ = jl; j_ <= jr; j_++)
								s += !check(i_, j_, 0, n - 1, jl, jr);
					}
				}
			}
		}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 0 / 20