Submission #427232

#	Time	Username	Problem	Language	Result	Execution time	Memory
427232		Pbezz	Rectangles (IOI19_rect)	C++14	15 / 100	5036 ms	100608 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;
int n,m;
int sparse[701][701][10];
int nearest[701][701][4];

void build(){

for(int s=1;s<10;s++){
	for(int i=0;i+(int)pow(2,s-1)<n;i++){
	for(int j=0;j<m;j++){
sparse[i][j][s]=max(sparse[i][j][s-1],sparse[i+(int)pow(2,s-1)][j][s-1]);
	}
	}
}

}

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

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=0;i<n;i++){
for(j=0;j<m;j++){
sparse[i][j][0] = nearest[i][j][1];
}
}

	build();

int mini1,mini2,mini3,mini0;
for(i=1;i<n-1;i++){
for(j=1;j<m-1;j++){
mini0=m;//cout<<i<<" "<<j<<endl;
	for(ii=i;ii<n-1;ii++){
mini0=min(mini0,nearest[ii][j-1][0]);
mini2=n;
mini3=-1;
int s=0;
while(2*(int)pow(2,s)<=ii-i+1)s++;

	for(jj=j;jj<min(m-1,mini0);jj++){//cout<<ii<<" "<<jj<<"  ";
ok=true;
//nearest[A][j-1][0] e minimo no segmento i,j-1 a ii,j-1

mini2 = min(mini2,nearest[i-1][jj][2]);
mini3 = max(mini3,nearest[ii+1][jj][3]);

//maximo de nearest no segmento i,jj+1 a ii,jj+1

mini1 = sparse[i][jj+1][s];
mini1 = max(mini1,sparse[ii-(int)pow(2,s)+1][jj+1][s]);

if(mini0<=jj||mini1>=j)ok=false;

if(mini2<=ii||mini3>=i)ok=false;

//cout<<mini0<<" "<<mini1<<" "<<mini2<<" "<<mini3<<" "<<s<<endl;



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: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28