Submission #723060

#	Time	Username	Problem	Language	Result	Execution time	Memory
723060		victor_gao	Rectangles (IOI19_rect)	C++17	27 / 100	5026 ms	112824 KiB

rect

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

void build(){
	for (int i=0;i<n;i++){
		vector<int>st;
		int last=0;
		for (int j=1;j<m;j++){
			int last=0;
			for (int k=j;k<m-1;k++){
				last=max(last,arr[i][k]);
				if (last<arr[i][j-1]&&last<arr[i][k+1])
					can[i][j-1].insert(k+1);
			}
		}
	}
}
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].begin();
				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].find(nxt)==can[k][j].end())
						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].erase(can[i][j].begin());
			}
		}
	}
	return ans;
}
/*
4 4
10 8 7 6 
9 4 4 5 
8 2 6 2 
3 8 9 10 
*/

Compilation message (stderr)

rect.cpp: In function 'void build()':
rect.cpp:12:7: warning: unused variable 'last' [-Wunused-variable]
   12 |   int last=0;
      |       ^~~~

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