Submission #1219653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219653		HappyCapybara	Rectangles (IOI19_rect)	C++17	0 / 100	1535 ms	608 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<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: 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