oj.uz

Submission #529918

# Submission time Handle Problem Language Result Execution time Memory
529918 2022-02-24T03:19:44 Z 8e7 Sandcastle 2 (JOI22_ho_t5) C++17
100 / 100
 1767 ms 18228 KB 
//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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 38 ms 18188 KB Output is correct
3 Correct 37 ms 17820 KB Output is correct
4 Correct 35 ms 18204 KB Output is correct
5 Correct 35 ms 18224 KB Output is correct
6 Correct 47 ms 18228 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 1 ms 824 KB Output is correct
9 Correct 10 ms 844 KB Output is correct
10 Correct 8 ms 828 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 10 ms 912 KB Output is correct
14 Correct 7 ms 756 KB Output is correct
15 Correct 10 ms 836 KB Output is correct
16 Correct 10 ms 900 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 1 ms 824 KB Output is correct
9 Correct 10 ms 844 KB Output is correct
10 Correct 8 ms 828 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 10 ms 912 KB Output is correct
14 Correct 7 ms 756 KB Output is correct
15 Correct 10 ms 836 KB Output is correct
16 Correct 10 ms 900 KB Output is correct
17 Correct 5 ms 2748 KB Output is correct
18 Correct 70 ms 2832 KB Output is correct
19 Correct 32 ms 2636 KB Output is correct
20 Correct 86 ms 2928 KB Output is correct
21 Correct 90 ms 2924 KB Output is correct
22 Correct 90 ms 2908 KB Output is correct
23 Correct 83 ms 2768 KB Output is correct
24 Correct 86 ms 2576 KB Output is correct
25 Correct 88 ms 2872 KB Output is correct
26 Correct 88 ms 2940 KB Output is correct
27 Correct 86 ms 2804 KB Output is correct
28 Correct 87 ms 2892 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 1 ms 824 KB Output is correct
9 Correct 10 ms 844 KB Output is correct
10 Correct 8 ms 828 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 10 ms 912 KB Output is correct
14 Correct 7 ms 756 KB Output is correct
15 Correct 10 ms 836 KB Output is correct
16 Correct 10 ms 900 KB Output is correct
17 Correct 5 ms 2748 KB Output is correct
18 Correct 70 ms 2832 KB Output is correct
19 Correct 32 ms 2636 KB Output is correct
20 Correct 86 ms 2928 KB Output is correct
21 Correct 90 ms 2924 KB Output is correct
22 Correct 90 ms 2908 KB Output is correct
23 Correct 83 ms 2768 KB Output is correct
24 Correct 86 ms 2576 KB Output is correct
25 Correct 88 ms 2872 KB Output is correct
26 Correct 88 ms 2940 KB Output is correct
27 Correct 86 ms 2804 KB Output is correct
28 Correct 87 ms 2892 KB Output is correct
29 Correct 43 ms 17796 KB Output is correct
30 Correct 495 ms 17120 KB Output is correct
31 Correct 1725 ms 17484 KB Output is correct
32 Correct 48 ms 17564 KB Output is correct
33 Correct 1673 ms 17968 KB Output is correct
34 Correct 1728 ms 17776 KB Output is correct
35 Correct 644 ms 11700 KB Output is correct
36 Correct 993 ms 17092 KB Output is correct
37 Correct 1677 ms 17428 KB Output is correct
38 Correct 1721 ms 17532 KB Output is correct
39 Correct 1721 ms 17544 KB Output is correct
40 Correct 1670 ms 17588 KB Output is correct
41 Correct 1661 ms 17612 KB Output is correct
42 Correct 1767 ms 17472 KB Output is correct
43 Correct 1712 ms 17424 KB Output is correct
44 Correct 1756 ms 17424 KB Output is correct