oj.uz

Submission #589516

# Submission time Handle Problem Language Result Execution time Memory
589516 2022-07-04T19:42:32 Z Soumya1 Rectangles (IOI19_rect) C++17
50 / 100
 538 ms 1048576 KB 
#include "rect.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
	#include <debug_local.h>
#endif
using namespace std;
long long count_rectangles(vector<vector<int>> a) {
	long long ans = 0;
	int n = a.size();
	int m = a[0].size();
	if (n <= 2) return 0;
	if (m <= 2) return 0;
	bool oneorzero = true;
	for (auto i : a) {
		for (int j : i) {
			oneorzero &= (j <= 1);
		}
	}
	if (n <= 3) {
		vector<int> ok(m);
		for (int i = 1; i < m - 1; i++) ok[i] = (a[0][i] > a[1][i] && a[2][i] > a[1][i]);
		for (int i = 1; i < m - 1; i++) {
			int cur_max = 0;
			for (int j = i; j < m - 1; j++) {
				if (!ok[j]) break;
				cur_max = max(cur_max, a[1][j]);
				if (a[1][i - 1] > cur_max && a[1][j + 1] > cur_max) ans++;	
			}
		}
		return ans;
	}
	if (oneorzero) {
		vector<vector<int>> p(n + 1, vector<int> (m + 1));
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + (a[i - 1][j - 1] ^ 1);
			}
		}
		auto sum = [&](int i, int j, int ii, int jj) {
			return p[ii][jj] - p[i - 1][jj] - p[ii][j - 1] + p[i - 1][j - 1];
		};
		vector<vector<int>> row(n, vector<int> (m));
		vector<vector<int>> col(m, vector<int> (n));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				row[i][j] = (j == 0 ? 0 : row[i][j - 1]) + a[i][j];
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				col[i][j] = (j == 0 ? 0 : col[i][j - 1]) + a[j][i];
			}
		}
		vector<vector<int>> to_right(n, vector<int> (m));
		auto to_down = to_right;
		for (int i = 0; i < n; i++) {
			for (int j = m - 1; j >= 0; j--) {
				if (a[i][j] == 1) to_right[i][j] = j;
				else to_right[i][j] = (j == m - 1 ? m : to_right[i][j + 1]);
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j < m; j++) {
				if (a[i][j] == 1) to_down[i][j] = i;
				else to_down[i][j] = (i == n - 1 ? n : to_down[i + 1][j]);
			}
		}
		for (int i = 1; i < n - 1; i++) {
			for (int j = 1; j < m - 1; j++) {
				if (a[i][j]) continue;
				if (to_right[i][j] >= m) continue;
				if (to_down[i][j] >= n) continue;
				int r = to_right[i][j], d = to_down[i][j];
				if (row[i - 1][r - 1] - row[i - 1][j - 1] != r - j) continue;
				if (row[d][r - 1] - row[d][j - 1] != r - j) continue;
				if (col[r][d - 1] - col[r][i - 1] != d - i) continue;
				if (col[j - 1][d - 1] - col[j - 1][i - 1] != d - i) continue;
				if (sum(i + 1, j + 1, d, r) != (d - i) * (r - j)) continue;
				ans++;
			}
		}
		return ans;
	}
	int max_val[n][n][m];
	bool good[n][n][m];
	memset(max_val, 0, sizeof max_val);
	memset(good, 0, sizeof good);
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < m - 1; j++) {
			for (int ii = i; ii < n - 1; ii++) {
				max_val[i][ii][j] = (i == ii ? a[i][j] : max(a[ii][j], max_val[i][ii - 1][j]));
				good[i][ii][j] = (max_val[i][ii][j] < min(a[i - 1][j], a[ii + 1][j]));
			}
		}
	}
	int mx[m][m][n];
	bool gg[m][m][n];
	memset(mx, 0, sizeof mx);
	memset(gg, 0, sizeof gg);
	for (int i = 1; i < m - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			for (int ii = i; ii < m - 1; ii++) {
				mx[i][ii][j] = (i == ii ? a[j][i] : max(a[j][ii], mx[i][ii - 1][j]));
				gg[i][ii][j] = (mx[i][ii][j] < min(a[j][i - 1], a[j][ii + 1]));
			}
		}
	}
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < m - 1; j++) {
			for (int ii = i; ii < n - 1; ii++) {
				for (int jj = j; jj < m - 1; jj++) {
					if (!good[i][ii][jj]) break;
					bool g = true;
					for (int x = i; x <= ii; x++) g &= gg[j][jj][x];
					if (g) ans++;
				}
			}
		}
	}
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 552 KB Output is correct
10 Correct 1 ms 548 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 292 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 552 KB Output is correct
10 Correct 1 ms 548 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 292 KB Output is correct
22 Correct 13 ms 5332 KB Output is correct
23 Correct 11 ms 5364 KB Output is correct
24 Correct 11 ms 5300 KB Output is correct
25 Correct 6 ms 5332 KB Output is correct
26 Correct 5 ms 5204 KB Output is correct
27 Correct 6 ms 5204 KB Output is correct
28 Correct 6 ms 5332 KB Output is correct
29 Correct 4 ms 2132 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 552 KB Output is correct
10 Correct 1 ms 548 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 13 ms 5332 KB Output is correct
18 Correct 11 ms 5364 KB Output is correct
19 Correct 11 ms 5300 KB Output is correct
20 Correct 6 ms 5332 KB Output is correct
21 Correct 5 ms 5204 KB Output is correct
22 Correct 6 ms 5204 KB Output is correct
23 Correct 6 ms 5332 KB Output is correct
24 Correct 4 ms 2132 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 292 KB Output is correct
30 Correct 295 ms 79176 KB Output is correct
31 Correct 300 ms 79104 KB Output is correct
32 Correct 290 ms 79180 KB Output is correct
33 Correct 101 ms 78924 KB Output is correct
34 Correct 79 ms 78924 KB Output is correct
35 Correct 88 ms 79088 KB Output is correct
36 Correct 81 ms 79128 KB Output is correct
37 Correct 88 ms 77420 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 552 KB Output is correct
10 Correct 1 ms 548 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 13 ms 5332 KB Output is correct
18 Correct 11 ms 5364 KB Output is correct
19 Correct 11 ms 5300 KB Output is correct
20 Correct 6 ms 5332 KB Output is correct
21 Correct 5 ms 5204 KB Output is correct
22 Correct 6 ms 5204 KB Output is correct
23 Correct 6 ms 5332 KB Output is correct
24 Correct 4 ms 2132 KB Output is correct
25 Correct 295 ms 79176 KB Output is correct
26 Correct 300 ms 79104 KB Output is correct
27 Correct 290 ms 79180 KB Output is correct
28 Correct 101 ms 78924 KB Output is correct
29 Correct 79 ms 78924 KB Output is correct
30 Correct 88 ms 79088 KB Output is correct
31 Correct 81 ms 79128 KB Output is correct
32 Correct 88 ms 77420 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 292 KB Output is correct
38 Runtime error 538 ms 1048576 KB Execution killed with signal 9
39 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 155 ms 83504 KB Output is correct
8 Correct 315 ms 172068 KB Output is correct
9 Correct 326 ms 172620 KB Output is correct
10 Correct 318 ms 172532 KB Output is correct
11 Correct 102 ms 85824 KB Output is correct
12 Correct 209 ms 161840 KB Output is correct
13 Correct 217 ms 172420 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 552 KB Output is correct
10 Correct 1 ms 548 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 13 ms 5332 KB Output is correct
18 Correct 11 ms 5364 KB Output is correct
19 Correct 11 ms 5300 KB Output is correct
20 Correct 6 ms 5332 KB Output is correct
21 Correct 5 ms 5204 KB Output is correct
22 Correct 6 ms 5204 KB Output is correct
23 Correct 6 ms 5332 KB Output is correct
24 Correct 4 ms 2132 KB Output is correct
25 Correct 295 ms 79176 KB Output is correct
26 Correct 300 ms 79104 KB Output is correct
27 Correct 290 ms 79180 KB Output is correct
28 Correct 101 ms 78924 KB Output is correct
29 Correct 79 ms 78924 KB Output is correct
30 Correct 88 ms 79088 KB Output is correct
31 Correct 81 ms 79128 KB Output is correct
32 Correct 88 ms 77420 KB Output is correct
33 Runtime error 538 ms 1048576 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -