Submission #867610

#TimeUsernameProblemLanguageResultExecution timeMemory
867610JakobZorzRectangles (IOI19_rect)C++17
72 / 100
5026 ms171944 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...