Submission #1290737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290737		enzy	Rectangles (IOI19_rect)	C++20	10 / 100	1 ms	344 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2502;
int val[maxn][maxn], v[maxn], pref[maxn], suf[maxn];
ll solve(int l, int r){
	if(l>r) return 0ll;
	pref[l-1]=v[l-1];
	suf[r+1]=v[r+1];
	for(int i=l;i<=r;i++) pref[i]=max(pref[i-1],v[i]);
	for(int i=r;i>=l;i--) suf[i]=max(suf[i+1],v[i]);
	ll ret=0;
	for(int i=l;i<=r;i++) if(pref[i]!=v[i]&&suf[i]!=v[i]) ret++;
	return ret;
}
ll count_rectangles(vector<vector<int> > a){
	int n=a.size(), m=a[0].size();
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			val[i+1][j+1]=a[i][j];
	if(min(n,m)<3) return 0ll;
	for(int i=1;i<=m;i++) v[i]=val[2][i];
	int last=0;
	ll resp=0;
	for(int i=1;i<=m;i++){
		if(val[2][i]>=min(val[1][i],val[3][i])){
			resp+=solve(last+1,i-1);
			last=i;
		}
	}
	resp+=solve(last+1,m);
	return resp;
}

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