Submission #589504

#	Time	Username	Problem	Language	Result	Execution time	Memory
589504		Soumya1	Rectangles (IOI19_rect)	C++17	10 / 100	144 ms	114456 KiB

rect

#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));
		auto col = row;
		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;
	}
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28