Submission #1219690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219690		HappyCapybara	Rectangles (IOI19_rect)	C++17	59 / 100	5104 ms	485596 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});
		}
	}
	set<vector<int>> cand;
	for (int i=1; i<n-1; i++){
		for (int j=1; j<m-1; j++){
			if (r[i][j-1] != -1){
				if (d[i-1][r[i][j-1]-1] != -1) cand.insert({i, d[i-1][r[i][j-1]-1]-1, j, r[i][j-1]-1});
				if (u[i+1][r[i][j-1]-1] != -1) cand.insert({u[i+1][r[i][j-1]-1]+1, i, j, r[i][j-1]-1});
				if (d[i-1][j] != -1) cand.insert({i, d[i-1][j]-1, j, r[i][j-1]-1});
				if (u[i+1][j] != -1) cand.insert({u[i+1][j]+1, i, j, r[i][j-1]-1});
			}
			if (l[i][j+1] != -1){
				if (d[i-1][l[i][j+1]+1] != -1) cand.insert({i, d[i-1][l[i][j+1]+1]-1, l[i][j+1]+1, j});
				if (u[i+1][l[i][j+1]+1] != -1) cand.insert({u[i+1][l[i][j+1]+1]+1, i, l[i][j+1]+1, j});
				if (d[i-1][j] != -1) cand.insert({i, d[i-1][j]-1, l[i][j+1]+1, j});
				if (u[i+1][j] != -1) cand.insert({u[i+1][j]+1, i, l[i][j+1]+1, j});
			}
			if (d[i-1][j] != -1){
				if (r[d[i-1][j]-1][j-1] != -1) cand.insert({i, d[i-1][j]-1, j, r[d[i-1][j]-1][j-1]-1});
				if (l[d[i-1][j]-1][j+1] != -1) cand.insert({i, d[i-1][j]-1, l[d[i-1][j]-1][j+1]+1, j});
				if (r[i][j-1] != -1) cand.insert({i, d[i-1][j]-1, j, r[i][j-1]-1});
				if (l[i][j+1] != -1) cand.insert({i, d[i-1][j]-1, l[i][j+1]+1, j});
			}
			if (u[i+1][j] != -1){
				if (r[u[i+1][j]+1][j-1] != -1) cand.insert({u[i+1][j]+1, i, j, r[u[i+1][j]+1][j-1]-1});
				if (l[u[i+1][j]+1][j+1] != -1) cand.insert({u[i+1][j]+1, i, l[u[i+1][j]+1][j+1]+1, j});
				if (r[i][j-1] != -1) cand.insert({u[i+1][j]+1, i, j, r[i][j-1]-1});
				if (l[i][j+1] != -1) cand.insert({u[i+1][j]+1, i, l[i][j+1]+1, j});
			}
		}
	}
	ll res = 0;
	for (vector<int> v : cand){
		int t = v[0], b = v[1], i = v[2], j = v[3];
		if (b < t || j < i) continue;
		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: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28