Submission #1237195

#TimeUsernameProblemLanguageResultExecution timeMemory
1237195Muhammad_AneeqRectangles (IOI19_rect)C++20
59 / 100
1850 ms1083328 KiB
#pragma GCC optimize("O2") #include "rect.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> int const N=2501,LG=12; struct spmx //sparse table for max { int sp[N][LG]={}; spmx(vector<int>vals) { int n=vals.size(); for (int i=0;i<n;i++) sp[i][0]=vals[i]; for (int j=1;(1<<j)<=n;j++) for (int i=0;i+(1<<j)-1<n;i++) sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]); } inline int get(int l,int r) { if (l>r) return 1e9; int lg=log2(r-l+1); return max(sp[l][lg],sp[r+1-(1<<lg)][lg]); } }; struct spmn //sparse table for min { int sp[N][LG]={}; spmn(vector<int>vals) { int n=vals.size(); for (int i=0;i<n;i++) sp[i][0]=vals[i]; for (int j=1;(1<<j)<=n;j++) for (int i=0;i+(1<<j)-1<n;i++) sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]); } inline int get(int l,int r) { if (l>r) return 0; int lg=log2(r-l+1); return min(sp[l][lg],sp[r+1-(1<<lg)][lg]); } }; int l[N][N],r[N][N],u[N][N],d[N][N]={}; int n,m; vector<spmn>mr,md; vector<spmx>ml,mu; inline bool check(int u,int d,int l,int r) { if (u==0||d==n-1||l==0||r==m-1) return 0; if (md[u-1].get(l,r)<d) return 0; if (mu[d+1].get(l,r)>u) return 0; if (ml[r+1].get(u,d)>l) return 0; if (mr[l-1].get(u,d)<r) return 0; return 1; } long long count_rectangles(vector<vector<int>>a) { n=a.size(),m=a[0].size(); vector<pair<pii,pii>>ans; for (int i=0;i<n;i++) { deque<pair<int,int>>vl; vl.push_back({-1,1e9}); for (int j=0;j<m;j++) { while (vl.size()&&vl.back().second<a[i][j]) vl.pop_back(); l[i][j]=vl.back().first+1; vl.push_back({j,a[i][j]}); } vl={}; vl.push_back({m,1e9}); for (int j=m-1;j>=0;j--) { while (vl.size()&&vl.back().second<a[i][j]) vl.pop_back(); r[i][j]=vl.back().first-1; vl.push_back({j,a[i][j]}); } } for (int i=0;i<m;i++) { deque<pair<int,int>>vl; vl.push_back({-1,1e9}); for (int j=0;j<n;j++) { while (vl.size()&&vl.back().second<a[j][i]) vl.pop_back(); u[j][i]=vl.back().first+1; vl.push_back({j,a[j][i]}); } vl={}; vl.push_back({n,1e9}); for (int j=n-1;j>=0;j--) { while (vl.size()&&vl.back().second<a[j][i]) vl.pop_back(); d[j][i]=vl.back().first-1; vl.push_back({j,a[j][i]}); } } for (int i=0;i<n;i++) { vector<int>u1,d1; for (int j=0;j<m;j++) { u1.push_back(u[i][j]); d1.push_back(d[i][j]); } mu.push_back(spmx(u1)); md.push_back(spmn(d1)); } for (int i=0;i<m;i++) { vector<int>l1,r1; for (int j=0;j<n;j++) { l1.push_back(l[j][i]); r1.push_back(r[j][i]); } ml.push_back(spmx(l1)); mr.push_back(spmn(r1)); } for (int i=0;i<n;i++) { deque<pair<int,int>>vl; vl.push_back({-1,1e9}); for (int j=0;j<m;j++) { while (vl.size()&&vl.back().second<=a[i][j]) vl.pop_back(); l[i][j]=vl.back().first+1; vl.push_back({j,a[i][j]}); } vl={}; vl.push_back({m,1e9}); for (int j=m-1;j>=0;j--) { while (vl.size()&&vl.back().second<=a[i][j]) vl.pop_back(); r[i][j]=vl.back().first-1; vl.push_back({j,a[i][j]}); } } for (int i=0;i<m;i++) { deque<pair<int,int>>vl; vl.push_back({-1,1e9}); for (int j=0;j<n;j++) { while (vl.size()&&vl.back().second<=a[j][i]) vl.pop_back(); u[j][i]=vl.back().first+1; vl.push_back({j,a[j][i]}); } vl={}; vl.push_back({n,1e9}); for (int j=n-1;j>=0;j--) { while (vl.size()&&vl.back().second<=a[j][i]) vl.pop_back(); d[j][i]=vl.back().first-1; vl.push_back({j,a[j][i]}); } } for (int i=1;i<n-1;i++) { for (int j=1;j<m-1;j++) { if (check(u[i][j],d[i][j],l[i][j],r[i][j])) { ans.push_back({{u[i][j],d[i][j]},{l[i][j],r[i][j]}}); } } } sort(begin(ans),end(ans)); int cnt=0; for (int i=0;i<ans.size();i++) { int j=i; while (j<ans.size()&&ans[i]==ans[j]) j++; cnt++; i=j-1; } return cnt; }
#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...