Submission #427224

#TimeUsernameProblemLanguageResultExecution timeMemory
427224PbezzRectangles (IOI19_rect)C++14
15 / 100
5052 ms100584 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back typedef pair<ll,ll> pii; const ll MAXN = 2e5+5; const ll INF = 1e9+7; int n,m; int sparse[701][701][10]; int nearest[701][701][4]; void build(){ for(int s=1;s<10;s++){ for(int i=0;i+(int)pow(2,s-1)<n;i++){ for(int j=0;j<m;j++){ sparse[i][j][s]=max(sparse[i][j][s-1],sparse[i+(int)pow(2,s-1)][j][s-1]); } } } } long long count_rectangles(std::vector<std::vector<int> > a) { int i,j,ii,jj; n=a.size();m=a[0].size(); ll ans=0; bool ok; stack<int>s; for(i=0;i<n;i++){//left while(!s.empty())s.pop(); for(j=m-1;j>=0;j--){ while(!s.empty() && a[i][s.top()]<a[i][j]){ s.pop(); } if(s.empty()){ nearest[i][j][0]=m; }else{ nearest[i][j][0]=s.top(); } s.push(j); } } for(i=0;i<n;i++){//right while(!s.empty())s.pop(); for(j=0;j<m;j++){ while(!s.empty() && a[i][s.top()]<a[i][j]){ s.pop(); } if(s.empty()){ nearest[i][j][1]=-1; }else{ nearest[i][j][1]=s.top(); } s.push(j); } } for(j=0;j<m;j++){//down while(!s.empty())s.pop(); for(i=n-1;i>=0;i--){ while(!s.empty() && a[s.top()][j]<a[i][j]){ s.pop(); } if(s.empty()){ nearest[i][j][2]=n; }else{ nearest[i][j][2]=s.top(); } s.push(i); } } for(j=0;j<m;j++){//up while(!s.empty())s.pop(); for(i=0;i<n;i++){ while(!s.empty() && a[s.top()][j]<a[i][j]){ s.pop(); } if(s.empty()){ nearest[i][j][3]=-1; }else{ nearest[i][j][3]=s.top(); } s.push(i); } } /* for(i=0;i<n;i++){ for(j=0;j<m;j++){ cout<<nearest[i][j][0]<<" "; }cout<<endl; }cout<<endl;*/ for(i=0;i<n;i++){ for(j=0;j<m;j++){ sparse[i][j][0] = nearest[i][j][1]; } } build(); int mini1,mini2,mini3,mini0; for(i=1;i<n-1;i++){ for(j=1;j<m-1;j++){ mini0=m;//cout<<i<<" "<<j<<endl; for(ii=i;ii<n-1;ii++){ mini0=min(mini0,nearest[ii][j-1][0]); mini2=n; mini3=-1; for(jj=j;jj<min(m-1,mini0);jj++){//cout<<ii<<" "<<jj<<" "; ok=true; //nearest[A][j-1][0] e minimo no segmento i,j-1 a ii,j-1 mini2 = min(mini2,nearest[i-1][jj][2]); mini3 = max(mini3,nearest[ii+1][jj][3]); //maximo de nearest no segmento i,jj+1 a ii,jj+1 int s=0; while(2*pow(2,s)<=ii-i+1)s++; mini1 = sparse[i][jj+1][s]; mini1 = max(mini1,sparse[ii-(int)pow(2,s)+1][jj+1][s]); if(mini0<=jj||mini1>=j)ok=false; if(mini2<=ii||mini3>=i)ok=false; //cout<<mini0<<" "<<mini1<<" "<<mini2<<" "<<mini3<<" "<<s<<endl; if(ok)ans++; } } } } /* 6 5 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 */ return ans; }
#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...