This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"rect.h"
#include<algorithm>
#include<unordered_set>
#include<set>
#include<iostream>
using namespace std;
typedef long long ll;
int gap_right[2500][2500];
int gap_down[2500][2500];
int gap_left[2500][2500];
int gap_up[2500][2500];
int arr[2500][2500];
int w,h;
int get_min_down(int y,int x1,int x2){
int res=2500;
for(int x=x1;x<x2;x++)
res=min(res,gap_down[x][y]);
return res;
}
int get_max_up(int y,int x1,int x2){
int res=-1;
for(int x=x1;x<x2;x++)
res=max(res,gap_up[x][y]);
return res;
}
int get_min_right(int x,int y1,int y2){
int res=2500;
for(int y=y1;y<y2;y++)
res=min(res,gap_right[x][y]);
return res;
}
int get_max_left(int x,int y1,int y2){
int res=-1;
for(int y=y1;y<y2;y++)
res=max(res,gap_left[x][y]);
return res;
}
void process_column(int x){
vector<pair<int,int>>vals;
for(int y=0;y<h;y++){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_up[x][y]=-1;
if(!vals.empty())
gap_up[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],y);
}
vals.clear();
for(int y=h-1;y>=0;y--){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_down[x][y]=2500;
if(!vals.empty())
gap_down[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],y);
}
}
void process_row(int y){
vector<pair<int,int>>vals;
for(int x=0;x<w;x++){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_left[x][y]=-1;
if(!vals.empty())
gap_left[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],x);
}
vals.clear();
for(int x=w;x>=0;x--){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_right[x][y]=2500;
if(!vals.empty())
gap_right[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],x);
}
}
int check1(int x1,int x2,int y){
if(x1==-1||x2==2500||x1==x2-1)
return 0;
int y1=y-1;
int y2=get_min_down(y1,x1+1,x2);
if(y2>=h)
return 0;
if(y1==y2-1)
return 0;
if(get_max_up(y2,x1+1,x2)>y1)
return 0;
if(get_min_right(x1,y1+1,y2)<x2)
return 0;
if(get_max_left(x2,y1+1,y2)>x1)
return 0;
for(int x=x1+1;x<x2;x++)
if(gap_down[x][y1]!=y2&&gap_up[x][y2]!=y1)
return 0;
for(int y=y1+1;y<y2;y++)
if(gap_right[x1][y]!=x2&&gap_left[x2][y]!=x1)
return 0;
return 1;
}
int check2(int x1,int x2,int y){
if(x1==-1||x2==2500||x1==x2-1)
return 0;
int y2=y+1;
int y1=get_max_up(y2,x1+1,x2);
if(y1==-1)
return 0;
if(y1==y2-1)
return 0;
if(get_min_down(y1,x1+1,x2)<y2)
return 0;
if(get_min_right(x1,y1+1,y2)<x2)
return 0;
if(get_max_left(x2,y1+1,y2)>x1)
return 0;
for(int x=x1+1;x<x2;x++)
if((gap_down[x][y1]!=y2&&gap_up[x][y2]!=y1)||gap_down[x][y1]==y2)
return 0;
for(int y=y1+1;y<y2;y++)
if(gap_right[x1][y]!=x2&&gap_left[x2][y]!=x1)
return 0;
return 1;
}
int check(int x1,int x2,int y){
return check1(x1,x2,y)+check2(x1,x2,y);
}
ll count_rectangles(vector<vector<int>>a_){
h=(int)a_.size();
w=(int)a_[0].size();
for(int x=0;x<w;x++){
for(int y=0;y<h;y++){
arr[x][y]=a_[y][x];
}
}
for(int x=0;x<w;x++)
process_column(x);
for(int y=0;y<h;y++)
process_row(y);
ll res=0;
for(int x=0;x<w;x++)
for(int y=1;y<h-1;y++){
res+=check(x,gap_right[x][y],y);
if(arr[gap_left[x][y]][y]!=arr[x][y])
res+=check(gap_left[x][y],x,y);
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |