Submission #836457

#TimeUsernameProblemLanguageResultExecution timeMemory
836457Rafi22Rectangles (IOI19_rect)C++14
27 / 100
5067 ms429776 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pb push_back #define st first #define nd second #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() int inf=1000000007; ll infl=1000000000000000007; const int N=2007,pot=1<<11; set<int>V[N][N]; int U[N][2*pot+7]; int D[N][2*pot+7]; int n,m; int queU(int v,int a,int b,int l,int r,int i) { if(a<=l&&b>=r) return U[i][v]; if(r<a||l>b) return -1; return max(queU(2*v,a,b,l,(l+r)/2,i),queU(2*v+1,a,b,(l+r)/2+1,r,i)); } int queD(int v,int a,int b,int l,int r,int i) { if(a<=l&&b>=r) return D[i][v]; if(r<a||l>b) return n; return min(queD(2*v,a,b,l,(l+r)/2,i),queD(2*v+1,a,b,(l+r)/2+1,r,i)); } ll count_rectangles(vector<vector<int>>a) { ll ans=0; n=sz(a),m=sz(a[0]); for(int i=1;i<n-1;i++) { deque<pair<int,int>>Q; Q.pb({a[i][0],0}); for(int j=1;j<m;j++) { while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back(); if(sz(Q)>0) V[Q.back().nd+1][j-1].insert(i); Q.pb({a[i][j],j}); } Q.clear(); Q.pb({a[i][m-1],m-1}); for(int j=m-2;j>=0;j--) { while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back(); if(sz(Q)>0) V[j+1][Q.back().nd-1].insert(i); Q.pb({a[i][j],j}); } } for(int i=0;i<n;i++) { for(int j=1;j<2*pot;j++) { U[i][j]=-1; D[i][j]=n; } } for(int j=0;j<m;j++) { deque<pair<int,int>>Q; Q.pb({a[0][j],0}); for(int i=1;i<n;i++) { while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back(); if(sz(Q)>0) U[i][j+pot]=Q.back().nd; Q.pb({a[i][j],i}); } Q.clear(); Q.pb({a[n-1][j],n-1}); for(int i=n-2;i>=0;i--) { while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back(); if(sz(Q)>0) D[i][j+pot]=Q.back().nd;; Q.pb({a[i][j],i}); } } for(int i=0;i<n;i++) { for(int j=pot-1;j>0;j--) { U[i][j]=max(U[i][2*j],U[i][2*j+1]); D[i][j]=min(D[i][2*j],D[i][2*j+1]); } } for(int i=0;i<m;i++) { for(int j=i;j<m;j++) { //cout<<i<<" "<<j<<endl; int p=0,l=-1; for(auto x:V[i][j]) { if(x!=l+1) p=x; l=x; for(int y=p;y<=x;y++) { // cout<<i<<" "<<j<<" "<<y<<" "<<x<<" "<<queD(1,i+1,j+1,1,pot,y-1)<<" "<<queU(1,i+1,j+1,1,pot,x+1)<<endl; if(queD(1,i+1,j+1,1,pot,y-1)>x&&queU(1,i+1,j+1,1,pot,x+1)<y) { //cout<<"TAK"<<endl; ans++; } } //cout<<"Xd "<<p<<" "<<x<<endl; //cout<<x<<endl; } //cout<<ans<<endl; } } return ans; } /* int main() { cout<<count_rectangles({ {4, 8, 7, 5, 6}, {7, 4, 10, 3, 5}, {9, 7, 20, 14, 2}, {9, 14, 7, 3, 6}, {5, 7, 5, 2, 7}, {4, 5, 13, 5, 6}})<<endl; return 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...