Submission #529901

#	Time	Username	Problem	Language	Result	Execution time	Memory
529901		8e7	Sandcastle 2 (JOI22_ho_t5)	C++17	71 / 100	5057 ms	17268 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 (k == 6 && i == 0 && j == 0) debug("upd", px, py, 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]++;
				else if (cnt == 2) p[k][i][j] += 2;
				if (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;
	};
	int ans = 0;
	for (int u = 0;u < n;u++) {
		for (int d = u;d < n;d++) {
			for (int l = 0;l < m;l++) {
				for (int r = l;r < m;r++) {
					ans += get_rect(u, d, l, r);
				}
			}
		}
	}
	cout << ans << endl;
}

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