제출 #1219652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219652		HappyCapybara	Rectangles (IOI19_rect)	C++17	0 / 100	4 ms	580 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;
				st.pop();
			}
			if (!st.empty()) 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;
				st.pop();
			}
			if (!st.empty()) 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<n-1; i++){
				for (int j=i; j<n-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: 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