Submission #589516

#	Time	Username	Problem	Language	Result	Execution time	Memory
589516		Soumya1	Rectangles (IOI19_rect)	C++17	50 / 100	538 ms	1048576 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));
		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 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28