oj.uz

Submission #614059

# Submission time Handle Problem Language Result Execution time Memory
614059 2022-07-30T17:41:44 Z valerikk Sandcastle 2 (JOI22_ho_t5) C++17
71 / 100
 63 ms 1208 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 7001;
const int M = 10000001;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int h, w;

struct Table {
	int a[N];

	int *operator[](int i) {
		return a + i * w;
	}

	Table() { 
		memset(a, 0, sizeof a); 
	}
} a, b, c[4], d[4];

int rmin[N], rmax[N];
long long rsum[N], rsumup[N], rsumdown[N];
int rcnt[N], rcntup[N], rcntdown[N];

int get_delta(int x, int y, int z) {
	int mn = M;
	for (int i = 0; i < 4; ++i) {
		if ((z >> i) & 1) continue;
		int xx = x + dx[i], yy = y + dy[i];
		if (xx >= 0 && xx < h && yy >= 0 && yy < w && a[xx][yy] > a[x][y] && a[xx][yy] < mn) mn = a[xx][yy];
	}
	return mn == M ? 0 : mn - a[x][y];
}

int main() {
	scanf("%d%d", &h, &w);
	for (int x = 0; x < h; ++x) {
		for (int y = 0; y < w; ++y) {
			scanf("%d", &a[x][y]);
		}
	}

	for (int x = 0; x < h; ++x) {
		for (int y = 0; y < w; ++y) {
			b[x][y] = get_delta(x, y, 0);
		}
	}
	for (int i = 0; i < 4; ++i) {
		for (int x = 0; x < h; ++x) {
			for (int y = 0; y < w; ++y) {
				c[i][x][y] = get_delta(x, y, 1 << i);
			}
		}
	}
	for (int i = 0; i < 4; ++i) {
		for (int x = 0; x < h; ++x) {
			for (int y = 0; y < w; ++y) {
				d[i][x][y] = get_delta(x, y, (1 << i) | (1 << ((i + 1) % 4)));
			}
		}
	}

	long long ans = h * w;

	for (int x = 0; x < h; ++x) {
		int len = 0;
		for (int y = 1; y < w; ++y) {
			++len;
			if (y == w - 1 || (a[x][y] < a[x][y + 1]) != (a[x][y - 1] < a[x][y])) {
				ans += 1ll * len * (len + 1) / 2;
				len = 0;
			}
		}
	}	
	for (int y = 0; y < w; ++y) {
		int len = 0;
		for (int x = 1; x < h; ++x) {
			++len;
			if (x == h - 1 || (a[x][y] < a[x + 1][y]) != (a[x - 1][y] < a[x][y])) {
				ans += 1ll * len * (len + 1) / 2;
				len = 0;
			}
		}
	}

	for (int y1 = 0; y1 < w; ++y1) {
		for (int x = 0; x < h; ++x) {
			rmin[x] = rmax[x] = a[x][y1];
			rsumup[x] = rsumdown[x] = rsum[x] = 0;
			rcntup[x] = rcntdown[x] = rcnt[x] = 0;
		}
		for (int y2 = y1 + 1; y2 < w; ++y2) {
			for (int x = 0; x < h; ++x) {
				rmin[x] = min(rmin[x], a[x][y2]);
				rmax[x] = max(rmax[x], a[x][y2]);
				if (y2 - 1 != y1) {
					rcntup[x] += c[0][x][y2 - 1] == 0;
					rsumup[x] += c[0][x][y2 - 1];
					rcntdown[x] += c[2][x][y2 - 1] == 0;
					rsumdown[x] += c[2][x][y2 - 1];	
					rcnt[x] += b[x][y2 - 1] == 0;
					rsum[x] += b[x][y2 - 1];
				}
			}
			for (int x = 0; x < h; ++x) {
				rcntup[x] += (d[3][x][y1] == 0) + (int)(d[0][x][y2] == 0);
				rsumup[x] += d[3][x][y1] + d[0][x][y2];
				rcntdown[x] += (d[2][x][y1] == 0) + (int)(d[1][x][y2] == 0);
				rsumdown[x] += d[2][x][y1] + d[1][x][y2];
				rcnt[x] += (c[3][x][y1] == 0) + (int)(c[1][x][y2] == 0);
				rsum[x] += c[3][x][y1] + c[1][x][y2];
			}
			for (int x1 = 0; x1 < h; ++x1) {
				long long sum = rsumup[x1];
				int cnt = rcntup[x1];
				int cmin = rmin[x1], cmax = rmax[x1];
				for (int x2 = x1 + 1; x2 < h; ++x2) {
					cmin = min(cmin, rmin[x2]);
					cmax = max(cmax, rmax[x2]);
					// if (x1 == 0 && x2 == 2 && y1 == 2 && y2 == 4) {
					// 	cerr << sum << " " << rsumdown[x2] << " " << cmax << " " << cmin << " " << cnt << " " << rcntdown[x2] << "\n";
					// }
					ans += sum + rsumdown[x2] == cmax - cmin && cnt + rcntdown[x2] == 1;
					cnt += rcnt[x2];
					sum += rsum[x2];
				}
			}
			for (int x = 0; x < h; ++x) {
				rcntup[x] -= (d[3][x][y1] == 0) + (int)(d[0][x][y2] == 0);
				rsumup[x] -= d[3][x][y1] + d[0][x][y2];
				rcntdown[x] -= (d[2][x][y1] == 0) + (int)(d[1][x][y2] == 0);
				rsumdown[x] -= d[2][x][y1] + d[1][x][y2];
				rcnt[x] -= (c[3][x][y1] == 0) + (int)(c[1][x][y2] == 0);
				rsum[x] -= c[3][x][y1] + c[1][x][y2];
			}
		}
	}
	
	printf("%lld\n", ans);

	return 0;	
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d", &h, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:42:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |    scanf("%d", &a[x][y]);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Runtime error 2 ms 1136 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 588 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 9 ms 624 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 3 ms 596 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 9 ms 624 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 31 ms 596 KB Output is correct
19 Correct 63 ms 652 KB Output is correct
20 Correct 43 ms 652 KB Output is correct
21 Correct 27 ms 652 KB Output is correct
22 Correct 26 ms 648 KB Output is correct
23 Correct 25 ms 596 KB Output is correct
24 Correct 20 ms 596 KB Output is correct
25 Correct 26 ms 596 KB Output is correct
26 Correct 27 ms 664 KB Output is correct
27 Correct 26 ms 596 KB Output is correct
28 Correct 30 ms 596 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 9 ms 624 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 31 ms 596 KB Output is correct
19 Correct 63 ms 652 KB Output is correct
20 Correct 43 ms 652 KB Output is correct
21 Correct 27 ms 652 KB Output is correct
22 Correct 26 ms 648 KB Output is correct
23 Correct 25 ms 596 KB Output is correct
24 Correct 20 ms 596 KB Output is correct
25 Correct 26 ms 596 KB Output is correct
26 Correct 27 ms 664 KB Output is correct
27 Correct 26 ms 596 KB Output is correct
28 Correct 30 ms 596 KB Output is correct
29 Runtime error 2 ms 1208 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -