제출 #1150970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150970		gyg	Rectangles (IOI19_rect)	C++20	0 / 100	55 ms	23880 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 = 2e2 + 5, M = 2e2 + 5;

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

arr<arr<arr<int, M>, M>, N> mx, vld, up, dwn, fr;
void prcmp() {
	for (int i = 1; i <= n; i++) {
		for (int l = 1; l <= m; l++) {
			for (int r = l; r <= m; r++) {
				mx[i][l][r] = max(mx[i][l][r - 1], a[i][r]);
				vld[i][l][r] = (l != 1 && r != m && mx[i][l][r] < a[i][l - 1] && mx[i][l][r] < a[i][r + 1]);
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int l = 1; l <= m; l++) {
			for (int r = l; r <= m; r++) {
				up[i][l][r] = 0, dwn[i][l][r] = n + 1, fr[i][l][r] = n + 1;
				
				for (int j = i - 1; j >= 1; j--) {
					if (mx[j][l][r] >= mx[i][l][r]) {
						up[i][l][r] = j;
						break;
					}
				}
				for (int j = i + 1; j <= n; j++) {
					if (mx[j][l][r] >= mx[i][l][r]) {
						dwn[i][l][r] = j;
						break;
					}
				}
				for (int j = i + 1; j <= n; j++) {
					if (!vld[j][l][r]) {
						fr[i][l][r] = j;
						break;
					}
				}
				
				// cout << i << " " << l << " " << r << ": " << mx[i][l][r] << endl;
				// cout << i << " " << l << " " << r << ": " << up[i][l][r] << endl;
			}
		}
	}

}

int cmp() {
	int ans = 0;
	for (int i = 1; i <= n - 2; i++) {
		for (int l = 2; l <= m - 1; l++) {
			for (int r = l; r <= m - 1; r++) {
				int j = min({fr[i][l][r], dwn[i][l][r], n});
				if (i + 2 > j) continue;
				int nw_ans = 0;
				for (int k = i + 2; k <= j; k++)
					nw_ans += (up[k][l][r] <= i);

				// cout << i << " " << l << " " << r << "; " << nw_ans << endl;

				ans += nw_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++)
			a[i][j] = _a[i - 1][j - 1];
	
	prcmp();
	int ans = cmp();
	return ans;
}
 

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