Submission #529918

#	Time	Username	Problem	Language	Result	Execution time	Memory
529918		8e7	Sandcastle 2 (JOI22_ho_t5)	C++17	100 / 100	1767 ms	18228 KiB

Main

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 105
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int main() {
	io
	int n, m;
	cin >> n >> m;
	bool sw = 0;
	if (n > m) swap(n, m), sw = 1; //n <= m
	vector<vector<int> > a(n, vector<int>(m, 0));
	vector<vector<vector<int> > > p(81, vector< vector<int> >(n, vector<int>(m)));
	vector<int> val;
	if (sw) {
		for (int i = 0;i < m;i++) {
			for (int j = 0;j < n;j++) cin >> a[j][i];
		}
	} else {
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < m;j++) cin >> a[i][j];
		}
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) val.push_back(a[i][j]);
	}
	sort(val.begin(), val.end());
	val.resize(int(unique(val.begin(), val.end()) - val.begin()));
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) a[i][j] = lower_bound(val.begin(), val.end(), a[i][j]) - val.begin() + 1;
	}
	
	auto check = [&] (int pv, int av, int cx, int cy) {
		return !(a[cx][cy] > av && a[cx][cy] < pv);
	};
	for (int k = 0;k < 81;k++) {
		int du = k%3, dr = (k/3)%3, dd = (k/9)%3, dl = (k/27);
		int d[4] = {du, dr, dd, dl};
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < m;j++) {	
				if (i < du || j < dl || n - i - 1 < dd || m - j - 1< dr) continue;
				int cnt = 0;
				for (int x = 0;x < 4;x++) {
					if (!d[x]) continue;	
					int px = i + dir[x][0], py = j + dir[x][1], pv = a[px][py];
					if (pv < a[i][j]) continue;
					bool con = 1;
					if (d[x] == 2) con &= check(pv, a[i][j], px+dir[x][0], py+dir[x][1]);	
					if (d[(x+1)%4]) con &= check(pv, a[i][j], px+dir[(x+1)%4][0], py+dir[(x+1)%4][1]);
					if (d[(x+3)%4]) con &= check(pv, a[i][j], px+dir[(x+3)%4][0], py+dir[(x+3)%4][1]);
					cnt += con ? 1 : 0;
				}
				if (cnt == 0) p[k][i][j]++;
			}
		}
		for (int i = 0;i < n;i++) {
			for (int j = 1;j < m;j++) p[k][i][j] += p[k][i][j-1];
			if (i) {
				for (int j = 0;j < m;j++) p[k][i][j] += p[k][i-1][j];
			}
		}
	}
	auto pref = [&](int k, int rx, int ry, int lx, int ly) {
		int ret = p[k][rx][ry];		
		if (lx) ret -= p[k][lx-1][ry];
		if (ly) ret -= p[k][rx][ly-1];
		if (lx&&ly) ret += p[k][lx-1][ly-1];
		return ret;
	};
	auto get_rect = [&] (int u, int d, int l, int r) {
		int tot = 0;
		for (int i = u;i <= d;i++) {
			int nx = i;
			if (i == u + 2 && d - u + 1 >= 5) nx = d - 2;
			for (int j = l;j <= r;j++) {
				int ny = j;
				if (j == l + 2 && r - l + 1 >= 5) ny = r - 2;		
				int du = min(i-u, 2), dr = min(r-j, 2), dd = min(d-i, 2), dl = min(j-l, 2);
				int state = du + dr*3 + dd*9 + dl*27;		
				tot += pref(state, nx, ny, i, j);
				//if (tot > 1) return 0;
				j = ny;
			}
			i = nx;
		}		
		//debug(u, d, l, r, tot);
		return tot == 1 ? 1 : 0;
	};
	
	vector<int> tmp(n*m, 0);
	int ans = 0;
	for (int u = 0;u < n;u++) {
		for (int d = u;d < n;d++) {
			vector<int> A(m), B(m), S(m);
			for (int r = 0;r < m;r++) {
				for (int i = u;i <= d;i++) {
					int nx = i;
					if (i == u + 2 && d - u + 1 >= 5) nx = d - 2;
					int du = min(i-u, 2), dd = min(d-i, 2), dl = 2, dr = 2;
					int state = du + dr*3 + dd*9 + dl*27;		
					S[r] += pref(state, nx, r, i, 0);

					if (r >= 3) {
						for (int j = r-1;j <= r;j++) {
							dl = 2, dr = r-j;
							state = du + dr*3 + dd*9 + dl*27;		
							B[r] += pref(state, nx, j, i, j);
						}
					}
					if (r < m - 1) {
						for (int j = r;j <= r+1;j++) {
							dl = j - r, dr = 2;
							state = du + dr*3 + dd*9 + dl*27;		
							A[r] += pref(state, nx, j, i, j);
						}
					}	

					i = nx;
				}
			}
			
			vector<int> re;
			for (int r = 0;r < m;r++) {
				for (int l = r;l >= r - 2;l--) ans += get_rect(u, d, l, r);
				if (r >= 3) {
					int add = -A[r-3] + S[r-2]+1;
					if (add >= 0) {
						re.push_back(add);
						tmp[add]++;
					}
					int val = B[r] + S[r-2] + 1;	
					//debug(r, val, tmp[val-1]);
					ans += tmp[val-1];
				}
			}	
			for (int i:re) tmp[i]--;
		}
	}
	cout << ans << endl;
}

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