Submission #1150977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150977		gyg	Rectangles (IOI19_rect)	C++20	15 / 100	27 ms	23108 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 80 + 5, M = 80 + 5;

int n, m;
arr<arr<int, M>, N> vl;

arr<arr<arr<bool, M>, M>, N> rw;
arr<arr<arr<bool, N>, N>, M> cl;
arr<arr<arr<int, M>, M>, N> rw_sm;
arr<arr<arr<int, N>, N>, M> cl_sm;
void prcmp() {
	for (int i = 1; i <= n; i++) {
		for (int l = 2; l <= m - 1; l++) {
			int mx = -1;
			for (int r = l; r <= m - 1; r++) {
				mx = max(mx, vl[i][r]);
				rw[i][l][r] = (mx >= vl[i][l - 1] || mx >= vl[i][r + 1]);
				rw_sm[i][l][r] = rw_sm[i - 1][l][r] + rw[i][l][r];
				// cout << i << " " << l << " " << r << ": " << rw[i][l][r] << endl;
			}
		}
	}

	for (int j = 1; j <= m; j++) {
		for (int l = 2; l <= n - 1; l++) {
			int mx = -1;
			for (int r = l; r <= n - 1; r++) {
				mx = max(mx, vl[r][j]);
				cl[j][l][r] = (mx >= vl[l - 1][j] || mx >= vl[r + 1][j]);
				cl_sm[j][l][r] = cl_sm[j - 1][l][r] + cl[j][l][r];
				// cout << j << " " << l << " " << r << ": " << cl[j][l][r] << endl;
			}
		}
	}
}

int cmp() {
	int ans = 0;
	for (int a = 2; a <= n - 1; a++) {
		for (int b = a; b <= n - 1; b++) {
			for (int c = 2; c <= m - 1; c++) {
				for (int d = c; d <= m - 1; d++) {
					if (rw_sm[b][c][d] - rw_sm[a - 1][c][d]) continue;
					if (cl_sm[d][a][b] - cl_sm[c - 1][a][b]) continue;
					// cout << a << " " << b << " " << c << " " << d << ": " << rw_sm[b][c][d] << endl;
					ans++;
				}	
			}
		}
	}
	return ans;
}

int count_rectangles(vec<vec<sig>> _a) {
	n = _a.size(), m = _a[0].size();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			vl[i][j] = _a[i - 1][j - 1];
	
	prcmp();
	return cmp();
}
 

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