Submission #1060087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060087		Unforgettablepl	Rectangles (IOI19_rect)	C++17	50 / 100	5065 ms	548176 KiB

rect

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

long long count_rectangles01(vector<vector<int>> a){
	int n = a.size();
	int m = a[0].size();
	long long ans = 0;
	vector visited = a;
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			if(visited[i][j])continue;
			int minx = n;
			int maxx = 0;
			int miny = m;
			int maxy = 0;
			int area = 0;
			function<void(int,int)> dfs = [&](int x,int y) {
				if(visited[x][y])return;
				visited[x][y]=true;
				area++;
				minx=min(minx,x);
				maxx=max(maxx,x);
				miny=min(miny,y);
				maxy=max(maxy,y);
				if(x!=0)dfs(x-1,y);
				if(y!=0)dfs(x,y-1);
				if(x!=n-1)dfs(x+1,y);
				if(y!=m-1)dfs(x,y+1);
			};
			dfs(i,j);
			if(minx==0)continue;
			if(miny==0)continue;
			if(maxx==n-1)continue;
			if(maxy==m-1)continue;
			if((maxx-minx+1)*(maxy-miny+1)==area)ans++;
		}
	}
	return ans;
}

long long count_rectangles(vector<vector<int>> a){
	{
		int maxi = 0;
		for(auto&i:a)for(int&j:i)maxi=max(maxi,j);
		if(maxi<=1)return count_rectangles01(a);
	}
	int n = a.size();
	int m = a[0].size();
	long long ans = 0;
	for(int i=0;i<m;i++) {
		vector<int> maxi(n);
		vector<bool> allowedrow(n);
		vector allowedranges(n,vector(n,0));
		for(int j=i+1;j<m-1;j++) {
			for(int k=0;k<n;k++) {
				maxi[k]=max(maxi[k],a[k][j]);
				allowedrow[k]=maxi[k]<a[k][i] and maxi[k]<a[k][j+1];
			}
			const int tar = j-i;
			{
				stack<pair<int,int>> s;
				int last_voilater = -1;
				for(int k=0;k<n;k++) {
					if(k!=0 and !allowedrow[k-1])last_voilater=k-1;
					while(!s.empty() and s.top().first<a[k][j])s.pop();
					if(s.empty()) {
						s.emplace(a[k][j],k);
						continue;
					}
					int l = s.top().second;l++;
					s.emplace(a[k][j],k);
					int r = s.top().second;r--;
					if(r<l)continue;
					allowedranges[l][r]++;
					if(l<=last_voilater)continue;
					if(allowedranges[l][r]==tar)ans++;
				}
			}
			{
				stack<pair<int,int>> s;
				int last_voilater = n;
				for(int k=n-1;k>=0;k--){
					if(k!=n-1 and !allowedrow[k+1])last_voilater=k+1;
					while(!s.empty() and s.top().first<a[k][j])s.pop();
					if(s.empty() or s.top().first==a[k][j]) {
						s.emplace(a[k][j],k);
						continue;
					}
					int r = s.top().second;r--;
					s.emplace(a[k][j],k);
					int l = s.top().second;l++;
					if(r<l)continue;
					allowedranges[l][r]++;
					if(last_voilater<=r)continue;
					if(allowedranges[l][r]==tar)ans++;
				}
			}
		}
	}
	return ans;
}

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