Submission #613826

#	Time	Username	Problem	Language	Result	Execution time	Memory
613826		valerikk	Sandcastle 2 (JOI22_ho_t5)	C++17	0 / 100	5048 ms	20476 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define all(a) begin(a), end(a)
#define sz(a) ((int) (a).size())

using ll = long long;
using ld = long double;

const int INF = 1e7 + 1;

const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};

vector<vector<ll>> get_prefs(const vector<vector<int>> &a) {
	int n = sz(a), m = sz(a[0]);
	vector<vector<ll>> p(n, vector<ll>(m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			p[i][j] = a[i][j];
			if (i != 0) p[i][j] += p[i - 1][j];
			if (j != 0) p[i][j] += p[i][j - 1];
			if (i != 0 && j != 0) p[i][j] -= p[i - 1][j - 1];
		}
	}
	return p;
}

ll get_sum(int i1, int j1, int i2, int j2, const vector<vector<ll>> &p) {
	if (i1 > i2 || j1 > j2) return 0;
	ll res = p[i2][j2];
	if (i1 != 0) res -= p[i1 - 1][j2];
	if (j1 != 0) res -= p[i2][j1 - 1];
	if (i1 != 0 && j1 != 0) res += p[i1 - 1][j1 - 1];
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, w;
	cin >> h >> w;
	vector a(h, vector<int>(w));
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			cin >> a[i][j];
		}
	}
	ll ans = h * w;
	for (int i = 0; i < h; ++i) {
		int len = 0;
		for (int j = 1; j < w; ++j) {
			++len;
			if (j == w - 1 || (a[i][j + 1] < a[i][j]) != (a[i][j] < a[i][j - 1])) {
				ans += 1ll * len * (len + 1) / 2;
				len = 0;
			}
		}
	}
	for (int j = 0; j < w; ++j) {
		int len = 0;
		for (int i = 1; i < h; ++i) {
			++len;
			if (i == h - 1 || (a[i + 1][j] < a[i][j]) != (a[i][j] < a[i - 1][j])) {
				ans += 1ll * len * (len + 1) / 2;
				len = 0;
			}
		}
	}
	vector d(1 << 4, vector<vector<int>>(h, vector<int>(w, 0)));
	vector c(1 << 4, vector<vector<int>>(h, vector<int>(w, 0)));
	for (int t = 0; t < (1 << 4); ++t) {
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < w; ++j) {
				int mn = INF;
				for (int k = 0; k < 4; ++k) {
					if (!((t >> k) & 1)) continue;
					int ii = i + di[k], jj = j + dj[k];
					if (ii < 0 || ii >= h || jj < 0 || jj >= w) continue;
					if (a[ii][jj] > a[i][j]) mn = min(mn, a[ii][jj]);
				}
				if (mn == INF) {
					c[t][i][j] = 1;
					d[t][i][j] = 0;
				} else {
					c[t][i][j] = 0;
					d[t][i][j] = mn - a[i][j];
				}
			}
		}
	}
	vector<vector<vector<ll>>> pd(1 << 4);
	vector<vector<vector<ll>>> pc(1 << 4);
	for (int t = 0; t < (1 << 4); ++t) {
		pd[t] = get_prefs(d[t]);
		pc[t] = get_prefs(c[t]);
	}
	for (int j1 = 0; j1 < w; ++j1) {
		vector<int> rmin(h, INF), rmax(h, 0);
		for (int i = 0; i < h; ++i) {
			rmin[i] = a[i][j1];
			rmax[i] = a[i][j1];
		}
		for (int j2 = j1 + 1; j2 < w; ++j2) {
			for (int i = 0; i < h; ++i) {
				rmin[i] = min(rmin[i], a[i][j2]);
				rmax[i] = max(rmax[i], a[i][j2]);
			}
			for (int i1 = 0; i1 < h; ++i1) {
				int cmin = rmin[i1], cmax = rmax[i1];
				for (int i2 = i1 + 1; i2 < h; ++i2) {
					cmin = min(cmin, rmin[i2]);
					cmax = max(cmax, rmax[i2]);
					ll sumd = get_sum(i1 + 1, j1 + 1, i2 - 1, j2 - 1, pd[(1 << 4) - 1]);
					sumd += get_sum(i1, j1 + 1, i1, j2 - 1, pd[(1 << 4) - 1 - (1 << 0)]);
					sumd += get_sum(i1 + 1, j2, i2 - 1, j2, pd[(1 << 4) - 1 - (1 << 1)]);
					sumd += get_sum(i2, j1 + 1, i2, j2 - 1, pd[(1 << 4) - 1 - (1 << 2)]);
					sumd += get_sum(i1 + 1, j1, i2 - 1, j2, pd[(1 << 4) - 1 - (1 << 3)]);
					sumd += d[(1 << 4) - (1 << 0) - (1 << 3)][i1][j1];
					sumd += d[(1 << 4) - (1 << 0) - (1 << 1)][i1][j2];
					sumd += d[(1 << 4) - (1 << 1) - (1 << 2)][i2][j2];
					sumd += d[(1 << 4) - (1 << 2) - (1 << 3)][i2][j1];
					ll sumc = get_sum(i1 + 1, j1 + 1, i2 - 1, j2 - 1, pc[(1 << 4) - 1]);
					sumc += get_sum(i1, j1 + 1, i1, j2 - 1, pc[(1 << 4) - 1 - (1 << 0)]);
					sumc += get_sum(i1 + 1, j2, i2 - 1, j2, pc[(1 << 4) - 1 - (1 << 1)]);
					sumc += get_sum(i2, j1 + 1, i2, j2 - 1, pc[(1 << 4) - 1 - (1 << 2)]);
					sumc += get_sum(i1 + 1, j1, i2 - 1, j2, pc[(1 << 4) - 1 - (1 << 3)]);
					sumc += c[(1 << 4) - (1 << 0) - (1 << 3)][i1][j1];
					sumc += c[(1 << 4) - (1 << 0) - (1 << 1)][i1][j2];
					sumc += c[(1 << 4) - (1 << 1) - (1 << 2)][i2][j2];
					sumc += c[(1 << 4) - (1 << 2) - (1 << 3)][i2][j1];
					if (sumc == 1 && sumd == cmax - cmin) {
						++ans;
					}		
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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