제출 #825392

#제출 시각아이디문제언어결과실행 시간메모리
825392FEDIKUSRectangles (IOI19_rect)C++17
72 / 100
5109 ms502392 KiB
#include "rect.h" #include<iostream> #include<vector> #include<stack> #include<set> #include<map> #include<algorithm> using namespace std; using ll = long long; using pii = pair<int,int>; const int maxn=2510; int n,m; vector<vector<int> > a; int ul[maxn][maxn],ud[maxn][maxn]; vector<pii> ver[maxn]; int bit[maxn]; void add(int x,int t=1){ x++; for(;x<maxn;x+=x&-x) bit[x]+=t; } int qry(int x){ int ret=0; x++; if(x==0) return 0; for(;x>0;x-=x&-x) ret+=bit[x]; return ret; } int query(int l,int r){ return qry(r)-qry(l-1); } int res=0; bool comp(tuple<int,int,int,int,int,int> &a,tuple<int,int,int,int,int,int> &b){ return get<4>(a)<get<4>(b); } ll count_rectangles(vector<vector<int> > _a){ swap(a,_a); n=a.size(); m=a[0].size(); for(int i=0;i<n;i++){ stack<int> stek; for(int j=0;j<m;j++){ while(!stek.empty() && a[i][stek.top()]<a[i][j]) stek.pop(); if(stek.empty()) ul[i][j]=-1; else ul[i][j]=stek.top(); stek.push(j); if(ul[i][j]==j-1) ul[i][j]=-1; } while(!stek.empty()) stek.pop(); for(int j=m-1;j>=0;j--){ while(!stek.empty() && a[i][stek.top()]<a[i][j]) stek.pop(); if(stek.empty()) ud[i][j]=-1; else ud[i][j]=stek.top(); stek.push(j); if(ud[i][j]==j+1) ud[i][j]=-1; if(ud[i][j]!=-1 && a[i][j]==a[i][ud[i][j]]) ud[i][j]=-1; } while(!stek.empty()) stek.pop(); } for(int i=0;i<m;i++){ stack<int> stek; for(int j=0;j<n;j++){ while(!stek.empty() && a[stek.top()][i]<a[j][i]) stek.pop(); if(!stek.empty()){ver[i].emplace_back(pii(stek.top(),j));} stek.push(j); } while(!stek.empty()) stek.pop(); for(int j=n-1;j>=0;j--){ while(!stek.empty() && a[stek.top()][i]<a[j][i]) stek.pop(); if(!stek.empty()){ver[i].emplace_back(pii(j,stek.top()));} stek.push(j); } while(!stek.empty()) stek.pop(); sort(ver[i].begin(),ver[i].end()); } bool prvi=true; vector<tuple<int,int,int,int,int,int> > sr; //col, vr, u, d, koji, res vector<tuple<int,int,int,int,int,int> > sl; for(int _=0;_<2;_++){ int klkr=0,klkl=0; // desni cosak map<pii,int> tren; for(int j=1;j<m;j++){ map<pii,int> novi; for(pii x:ver[j]){ if(x.second-x.first==1) continue; if(tren.find(x)==tren.end()) novi[x]=j; else novi[x]=tren[x]; } for(auto x:tren){ int u,d,r,l; u=x.first.first; d=x.first.second; r=j; l=x.second-1; if(ul[u+1][r]==-1) continue; if(ul[u+1][r]<l) continue; l=ul[u+1][r]; if(prvi){ sr.push_back({l,r,u+1,d-1,klkr++,-1}); sl.push_back({r,l,u+1,d-1,klkl++,-1}); continue; }else if(get<5>(sr[klkr++])+get<5>(sl[klkl++])!=d-u-1) continue; #ifdef DEBUG cout<<u<<" "<<d<<" "<<l<<" "<<r<<"\n"; #endif res++; } swap(tren,novi); } tren.clear(); // levi cosak for(int j=m-2;j>=0;j--){ map<pii,int> novi; for(pii x:ver[j]){ if(x.second-x.first==1) continue; if(tren.find(x)==tren.end()) novi[x]=j; else novi[x]=tren[x]; } for(auto x:tren){ int u,d,r,l; u=x.first.first; d=x.first.second; l=j; r=x.second+1; if(ud[u+1][l]==-1) continue; if(ud[u+1][l]>r) continue; r=ud[u+1][l]; if(prvi){ sr.push_back({l,r,u+1,d-1,klkr++,-1}); sl.push_back({r,l,u+1,d-1,klkl++,-1}); continue; }else if(get<5>(sr[klkr++])+get<5>(sl[klkl++])!=d-u-1) continue; #ifdef DEBUG cout<<u<<" "<<d<<" "<<l<<" "<<r<<"\n"; #endif res++; } swap(tren,novi); } tren.clear(); if(!prvi) break; sort(sl.begin(),sl.end()); sort(sr.begin(),sr.end()); prvi=false; int pcol=-1; int pvr=-1; map<int,vector<int> > gde; for(auto &x:sr){ auto [col,vr,u,d,koji,res]=x; if(col!=pcol){ gde.clear(); for(int i=0;i<maxn;i++) bit[i]=0; for(int i=0;i<n;i++) gde[ud[i][col]].push_back(i); pvr=-1; pcol=col; } if(vr!=pvr){ if(pvr!=-1) for(int i:gde[pvr]) add(i,-1); for(int i:gde[vr]) add(i,1); pvr=vr; } get<5>(x)=query(u,d); } pcol=-1; pvr=-1; gde.clear(); for(auto &x:sl){ auto [col,vr,u,d,koji,res]=x; if(col!=pcol){ gde.clear(); for(int i=0;i<maxn;i++) bit[i]=0; for(int i=0;i<n;i++) gde[ul[i][col]].push_back(i); pvr=-1; pcol=col; } if(vr!=pvr){ if(pvr!=-1) for(int i:gde[pvr]) add(i,-1); for(int i:gde[vr]) add(i,1); pvr=vr; } get<5>(x)=query(u,d); } sort(sl.begin(),sl.end(),comp); sort(sr.begin(),sr.end(),comp); } 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...