Submission #723066

#	Time	Username	Problem	Language	Result	Execution time	Memory
723066		victor_gao	Rectangles (IOI19_rect)	C++17	8 / 100	5055 ms	59056 KiB

rect

#pragma GCC optimize("Ofast,unroll-loops")
#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define N 2505
using namespace std;
int arr[N][N],n,m,mx[N];
bitset<10>can[N][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][k+1]=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++){
			if (n<=m) arr[i][j]=a[i][j];
			else arr[j][i]=a[i][j];
		}
	}
	if (n>m) swap(n,m);
	build();
	for (int i=1;i<n-1;i++){
		for (int j=0;j<m;j++){
			for (int nxt=j;nxt<m;nxt++){
				if (!can[i][j][nxt]) continue;
				for (int k=j;k<nxt;k++) mx[k]=0;
				for (int k=i;k<n-1;k++){
					if (!can[k][j][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;
					ans+=add;
				}
			}
		}
	}
	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: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28