제출 #825423

#제출 시각아이디문제언어결과실행 시간메모리
825423FEDIKUSRectangles (IOI19_rect)C++17
72 / 100
5035 ms503020 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; const int maxa=7e6+10; 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()); ver[i].resize(unique(ver[i].begin(),ver[i].end())-ver[i].begin()); } 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 vector<tuple<int,int,int> > tren; for(int j=1;j<m;j++){ vector<tuple<int,int,int> > novi; for(pii x:ver[j]){ if(x.second-x.first==1) continue; auto it=lower_bound(tren.begin(),tren.end(),tuple<int,int,int>(x.first,x.second,-1)); if(it==tren.end() || get<0>(*it)!=x.first || get<1>(*it)!=x.second) novi.push_back({x.first,x.second,j}); else novi.push_back({x.first,x.second,get<2>(*it)}); } for(auto x:tren){ int u,d,r,l; u=get<0>(x); d=get<1>(x); r=j; l=get<2>(x)-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--){ vector<tuple<int,int,int> > novi; for(pii x:ver[j]){ if(x.second-x.first==1) continue; auto it=lower_bound(tren.begin(),tren.end(),tuple<int,int,int>(x.first,x.second,-1)); if(it==tren.end() || get<0>(*it)!=x.first || get<1>(*it)!=x.second) novi.push_back({x.first,x.second,j}); else novi.push_back({x.first,x.second,get<2>(*it)}); } for(auto x:tren){ int u,d,r,l; u=get<0>(x); d=get<1>(x); l=j; r=get<2>(x)+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; vector<pair<int,int> > kolona; int tc=0; for(auto &x:sr){ auto [col,vr,u,d,koji,res]=x; if(col!=pcol){ kolona.clear(); for(int i=0;i<maxn;i++) bit[i]=0; for(int i=0;i<n;i++) kolona.push_back(pii(ud[i][col],i)); sort(kolona.begin(),kolona.end()); pvr=-1; tc=0; pcol=col; } if(vr!=pvr){ if(pvr!=-1){ int sta=tc-1; while(sta>=0 && kolona[sta].first==pvr){ add(kolona[sta].second,-1); sta--; } } while(tc<int(kolona.size()) && kolona[tc].first<=vr){ if(kolona[tc].first==vr) add(kolona[tc].second,1); tc++; } pvr=vr; } get<5>(x)=query(u,d); } pcol=-1; pvr=-1; kolona.clear(); tc=0; for(auto &x:sl){ auto [col,vr,u,d,koji,res]=x; if(col!=pcol){ kolona.clear(); for(int i=0;i<maxn;i++) bit[i]=0; for(int i=0;i<n;i++) kolona.push_back(pii(ul[i][col],i)); sort(kolona.begin(),kolona.end()); pvr=-1; tc=0; pcol=col; } if(vr!=pvr){ if(pvr!=-1){ int sta=tc-1; while(sta>=0 && kolona[sta].first==pvr){ add(kolona[sta].second,-1); sta--; } } while(tc<int(kolona.size()) && kolona[tc].first<=vr){ if(kolona[tc].first==vr) add(kolona[tc].second,1); tc++; } 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...