Submission #427083

#	Time	Username	Problem	Language	Result	Execution time	Memory
427083		Pbezz	Rectangles (IOI19_rect)	C++14	37 / 100	5049 ms	67600 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;

long long count_rectangles(std::vector<std::vector<int> > a) {
	ll n=a.size(),m=a[0].size(),i,j,ii,jj,A,B,ans=0;
bool ok;

int nearest[n+1][m+1][4];
stack<int>s;

for(i=0;i<n;i++){//left
while(!s.empty())s.pop();
for(j=m-1;j>=0;j--){

while(!s.empty() && a[i][s.top()]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][0]=m;
}else{
nearest[i][j][0]=s.top();
}
s.push(j);
}
}

for(i=0;i<n;i++){//right
while(!s.empty())s.pop();
for(j=0;j<m;j++){

while(!s.empty() && a[i][s.top()]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][1]=-1;
}else{
nearest[i][j][1]=s.top();
}
s.push(j);
}
}

for(j=0;j<m;j++){//down
while(!s.empty())s.pop();
for(i=n-1;i>=0;i--){

while(!s.empty() && a[s.top()][j]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][2]=n;
}else{
nearest[i][j][2]=s.top();
}
s.push(i);
}
}

for(j=0;j<m;j++){//up
while(!s.empty())s.pop();
for(i=0;i<n;i++){

while(!s.empty() && a[s.top()][j]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][3]=-1;
}else{
nearest[i][j][3]=s.top();
}
s.push(i);
}
}
/*
for(i=0;i<n;i++){
for(j=0;j<m;j++){

cout<<nearest[i][j][0]<<" ";

	}cout<<endl;
	}cout<<endl;*/

for(i=1;i<n-1;i++){
for(j=1;j<m-1;j++){

	for(ii=i;ii<n-1;ii++){
	for(jj=j;jj<m-1;jj++){
ok=true;

for(A=i;A<=ii;A++){//verificar esta

if(nearest[A][j-1][0]<=jj || nearest[A][jj+1][1]>=j ){
ok=false;
break;
}
}
if(!ok)continue;

for(B=j;B<=jj;B++){//verificar esta

if(nearest[i-1][B][2]<=ii || nearest[ii+1][B][3]>=i){
ok=false;
break;
}
}
if(ok)ans++;

	}
	}

}
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/


	return ans;
}

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