제출 #835812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835812		Lobo	Rectangles (IOI19_rect)	C++17	25 / 100	5082 ms	84368 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(),x.end()

const int maxn = 2550;
int n, m, a[maxn][maxn];
int lf[maxn][maxn], rg[maxn][maxn], up[maxn][maxn], dw[maxn][maxn];
set<pair<pair<int,int>,pair<int,int>>> ans;
int check(int r1, int r2, int c1, int c2) {
	if(c1 == 0 || c2 == m-1 || r1 == 0 || r2 == n-1) return 0;

	int mxlf = -1;
	for(int i = r1; i <= r2; i++) mxlf = max(mxlf,lf[i][c2+1]);
	int mnrg = m;
	for(int i = r1; i <= r2; i++) mnrg = min(mnrg,rg[i][c1-1]);
	int mxup = -1;
	for(int j = c1; j <= c2; j++) mxup = max(mxup,up[r2+1][j]);
	int mndw = n;
	for(int j = c1; j <= c2; j++) mndw = min(mndw,dw[r1-1][j]);

	if(mxlf < c1 && mnrg > c2 && mxup < r1 && mndw > r2) return 1;
	return 0;
}

long long count_rectangles(std::vector<std::vector<int>> A) {
	n = A.size();
	m = A[0].size();
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			a[i][j] = A[i][j];
		}
	}

	// primeiro >=
	for(int i = 0; i < n; i++) {
		stack<pair<int,int>> stk;
		// left
		for(int j = 0; j < m; j++) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) lf[i][j] = -1;
			else lf[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],j));
		}

		while(stk.size()) stk.pop();

		// right
		for(int j = m-1; j >= 0; j--) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) rg[i][j] = m;
			else rg[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],j));
		}
	}

	for(int j = 0; j < m; j++) {
		stack<pair<int,int>> stk;
		//up
		for(int i = 0; i < n; i++) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) up[i][j] = -1;
			else up[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],i));
		}

		while(stk.size()) stk.pop();

		// down
		for(int i = n-1; i >= 0; i--) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) dw[i][j] = n;
			else dw[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],i));
		}
	}

	for(int r1 = 1; r1 < n-1; r1++) {
		for(int r2 = r1; r2 < n-1; r2++) {
			for(int c1 = 1; c1 < m-1; c1++) {
				for(int c2 = c1; c2 < m-1; c2++) {
					if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
				}
			}
		}
	}

	return ans.size();
}

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