Submission #290424

#	Time	Username	Problem	Language	Result	Execution time	Memory
290424		ChrisT	Rectangles (IOI19_rect)	C++17	10 / 100	830 ms	1048576 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
long long subtask (vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	vector<vector<int>> psa(n,vector<int>(m));
	auto query = [&] (int x, int y, int x2, int y2) {
		return psa[x2][y2] - psa[x2][y-1] - psa[x-1][y2] + psa[x-1][y-1];
	};
	int high = 0, low = n, left = m, right = 0;
	function<void(int,int)> dfs = [&] (int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= m || a[x][y]) return;
		a[x][y] = 1; high = max(high,x); low = min(low,x); right = max(right,y); left = min(left,y);
		dfs(x-1,y); dfs(x+1,y); dfs(x,y+1); dfs(x,y-1);
	};
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) if (!a[i][j]) {
			high = right = 0;
			low = n; left = m;
			dfs(i,j);
			if (left > 0 && low > 0 && right + 1 < m && high + 1 < n && !query(low,left,high,right)) ++ans;
		}
	}
	return ans;
}
long long count_rectangles (vector<vector<int>> a) {
	int mxall = 0;
	for (auto &v : a) for (auto &i : v) mxall = max(mxall,i);
	if (mxall <= 1) return subtask(a);
	int n = a.size(), m = a[0].size();
	vector<vector<vector<bool>>> canV(m,vector<vector<bool>>(n,vector<bool>(n)));
	vector<vector<vector<bool>>> canH(n,vector<vector<bool>>(m,vector<bool>(m)));
	vector<vector<vector<int>>> psaV(n,vector<vector<int>>(n,vector<int>(m)));
	vector<vector<vector<int>>> psaH(m,vector<vector<int>>(m,vector<int>(n)));
	for (int i = 1; i + 1 < n; i++) {
		for (int j = 1; j + 1 < m; j++) {
			int mx = a[i][j];
			for (int k = j; k + 1 < m; k++) {
				mx = max(mx,a[i][k]);
				canH[i][j][k] = a[i][j-1] > mx && a[i][k+1] > mx;
			}
		}
	}
	for (int j = 1; j + 1 < m; j++) {
		for (int k = j; k + 1 < m; k++) {
			for (int i = 1; i + 1 < n; i++) {
				psaH[j][k][i] = psaH[j][k][i-1] + !canH[i][j][k];
			}
		}
	}
	for (int i = 1; i + 1 < m; i++) {
		for (int j = 1; j + 1 < n; j++) {
			int mx = a[j][i];
			for (int k = j; k + 1 < n; k++) {
				mx = max(mx,a[k][i]);
				canV[i][j][k] = a[j-1][i] > mx && a[k+1][i] > mx;
			}
		}
	}
	for (int j = 1; j + 1 < n; j++) {
		for (int k = j; k + 1 < n; k++) {
			for (int i = 1; i + 1 < m; i++) {
				psaV[j][k][i] = psaV[j][k][i-1] + !canV[i][j][k];
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i + 1 < n; i++) {
		for (int j = i; j + 1 < n; j++) { //rows[i --> j]
			for (int k = 1; k + 1 < m; k++) {
				for (int l = k; l + 1 < m; l++) { //cols[k --> l]
					ans += psaV[i][j][l] == psaV[i][j][k-1] && psaH[k][l][j] == psaH[k][l][i-1];
				}
			}
		}
	}
	return ans;
}

• 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