제출 #1219668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219668		HappyCapybara	Rectangles (IOI19_rect)	C++17	25 / 100	5096 ms	67912 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll count_rectangles(vector<vector<int>> a){
	int n = a.size(), m = a[0].size();
	vector<vector<int>> l(n, vector<int>(m, -1)), r(n, vector<int>(m, -1)), u(n, vector<int>(m, -1)), d(n, vector<int>(m, -1));
	stack<pair<int,int>> st;
	for (int i=0; i<n; i++){
		while (!st.empty()) st.pop();
		for (int j=0; j<m; j++){
			while (!st.empty() && st.top().first <= a[i][j]){
				r[i][st.top().second] = j;
				if (st.top().first == a[i][j]) l[i][j] = st.top().second;
				st.pop();
			}
			if (!st.empty() && l[i][j] == -1) l[i][j] = st.top().second;
			st.push({a[i][j], j});
		}
	}
	for (int j=0; j<m; j++){
		while (!st.empty()) st.pop();
		for (int i=0; i<n; i++){
			while (!st.empty() && st.top().first <= a[i][j]){
				d[st.top().second][j] = i;
				if (st.top().first == a[i][j]) u[i][j] = st.top().second;
				st.pop();
			}
			if (!st.empty() && u[i][j] == -1) u[i][j] = st.top().second;
			st.push({a[i][j], i});
		}
	}
	ll res = 0;
	for (int t=1; t<n-1; t++){
		for (int b=t; b<n-1; b++){
			for (int i=1; i<m-1; i++){
				for (int j=i; j<m-1; j++){
					bool valid = true;
					for (int row=t; row<=b; row++){
						if (r[row][i-1] != j+1 && l[row][j+1] != i-1) valid = false;
					}
					for (int col=i; col<=j; col++){
						if (d[t-1][col] != b+1 && u[b+1][col] != t-1) valid = false;
					}
					if (valid) res++;
				}
			}
		}
	}
	return res;
}

• 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