제출 #144084

#제출 시각아이디문제언어결과실행 시간메모리
144084LyestriaRectangles (IOI19_rect)C++14
72 / 100
5050 ms432684 KiB
#include "rect.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mn=2510; struct seg{ int seg[mn*2]; inline void up(int a,int b){ seg[a+=mn]=b; for(a>>=1;a;a>>=1)seg[a]=min(seg[a<<1],seg[(a<<1)^1]); } inline int qu(int a,int b){ int ans=0x3f3f3f3f; for(a+=mn,b+=mn;a<=b;a>>=1,b>>=1){ if(a&1)ans=min(ans,seg[a++]); if(!(b&1))ans=min(ans,seg[b--]); } return ans; } }; seg lef[mn],rig[mn],up[mn],dow[mn]; int elef[mn][mn],erig[mn][mn],eup[mn][mn],edow[mn][mn]; set<ll>ss; long long hsh(ll a,ll b,ll c,ll d){ return (a<<48)|(b<<32)|(c<<16)|d; } long long count_rectangles(std::vector<std::vector<int> > a) { int n=a.size(),m=a[0].size(); int i,j; for(i=0;i<n;i++){ stack<int>s; for(j=0;j<m;j++){ while(s.size()&&a[i][s.top()]<=a[i][j])rig[s.top()].up(i,j),s.pop(); s.push(j); } while(s.size())rig[s.top()].up(i,j),s.pop(); for(j=m-1;j>=0;j--){ while(s.size()&&a[i][s.top()]<=a[i][j])lef[s.top()].up(i,-j),s.pop(); s.push(j); } while(s.size())lef[s.top()].up(i,-j),s.pop(); for(j=0;j<m;j++){ while(s.size()&&a[i][s.top()]<a[i][j])erig[i][s.top()]=j,s.pop(); s.push(j); } while(s.size())erig[i][s.top()]=j,s.pop(); for(j=m-1;j>=0;j--){ while(s.size()&&a[i][s.top()]<a[i][j])elef[i][s.top()]=j,s.pop(); s.push(j); } while(s.size())elef[i][s.top()]=j,s.pop(); } for(i=0;i<m;i++){ stack<int>s; for(j=0;j<n;j++){ while(s.size()&&a[s.top()][i]<=a[j][i])dow[s.top()].up(i,j),s.pop(); s.push(j); } while(s.size())dow[s.top()].up(i,j),s.pop(); for(j=n-1;j>=0;j--){ while(s.size()&&a[s.top()][i]<=a[j][i])up[s.top()].up(i,-j),s.pop(); s.push(j); } while(s.size())up[s.top()].up(i,-j),s.pop(); for(j=0;j<n;j++){ while(s.size()&&a[s.top()][i]<a[j][i])edow[s.top()][i]=j,s.pop(); s.push(j); } while(s.size())edow[s.top()][i]=j,s.pop(); for(j=n-1;j>=0;j--){ while(s.size()&&a[s.top()][i]<a[j][i])eup[s.top()][i]=j,s.pop(); s.push(j); } while(s.size())eup[s.top()][i]=j,s.pop(); } int ans=0; for(i=1;i<n-1;i++){ for(j=1;j<m-1;j++){ int d,u,l,r; d=edow[i][j]; u=eup[i][j]; l=elef[i][j]; r=erig[i][j]; if(l==-1||u==-1||r==m||d==n)continue; if(rig[l].qu(u+1,d-1)<r)continue; if(-lef[r].qu(u+1,d-1)>l)continue; if(dow[u].qu(l+1,r-1)<d)continue; if(-up[d].qu(l+1,r-1)>u)continue; ss.insert(hsh(d,u,l,r)); } } return ss.size(); }

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:76:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans=0;
      ^~~
#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...