Submission #723052

#	Time	Username	Problem	Language	Result	Execution time	Memory
723052		victor_gao	Rectangles (IOI19_rect)	C++17	0 / 100	565 ms	935328 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define N 805
using namespace std;
deque<int>can[N][N];
int arr[N][N],n,m,mx[N];

void build(){
	for (int i=0;i<n;i++){
		vector<int>st;
		st.push_back(0);
		for (int j=1;j<m;j++){
			int last=0;
			while (!st.empty()&&arr[i][st.back()]<arr[i][j]){
				int p1=st.back(); st.pop_back();
				if (j-p1>=2&&last<arr[i][j]&&last<arr[i][p1])
					can[i][p1].push_back(j);
				if (!st.empty()&&p1-st.back()>=2)
					can[i][st.back()].push_back(p1);
				last=max(last,arr[i][p1]);
			}
			st.push_back(j);
		}
		while (!st.empty()){
			int p1=st.back(); st.pop_back();
			if (!st.empty()&&p1-st.back()>=2)
				can[i][st.back()].push_back(p1);
		}
	}
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size(); m=a[0].size();
	ll ans=0;
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++)
			arr[i][j]=a[i][j];
	}
	build();
	for (int i=1;i<n-1;i++){
		for (int j=0;j<m;j++){
		//	cout<<i<<" "<<j<<" size "<<can[i][j].size()<<'\n';
			while (!can[i][j].empty()){
				int nxt=can[i][j].front();
				for (int k=j;k<nxt;k++) mx[k]=0;
				for (int k=i;k<n-1;k++){
					if (can[k][j].empty()||can[k][j].front()!=nxt)
						break;
					int add=1;
					for (int l=j+1;l<nxt;l++){
						mx[l]=max(mx[l],arr[k][l]);
						if (mx[l]>=arr[i-1][l]){
							add=-1;
							break;
						}
						if (mx[l]>=arr[k+1][l])
							add=0;
					}
					if (add==-1) break;
				//	cout<<"add "<<i<<" "<<j<<" to "<<k<<" "<<nxt<<" -> "<<add<<'\n';
					ans+=add;
				}
			//	cout<<"after "<<i<<" "<<j<<"~"<<nxt<<" is "<<ans<<'\n';
				can[i][j].pop_front();
			}
		}
	}
	return ans;
}
/*
4 4
10 8 7 6 
9 4 4 5 
8 2 6 2 
3 8 9 10 


*/

• 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