제출 #443350

#제출 시각아이디문제언어결과실행 시간메모리
443350vanicRectangles (IOI19_rect)C++14
37 / 100
5099 ms576656 KiB
#include "rect.h" #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <array> using namespace std; typedef long long ll; const int mod=1e9+7, p=2503; inline int sum(int a, int b){ if(a+b>=mod){ return a+b-mod; } if(a+b<0){ return a+b+mod; } return a+b; } inline int mul(int a, int b){ return (ll)a*b%mod; } inline int pretvori(int a[4]){ int br=0; for(int i=0; i<4; i++){ br=mul(br, p); br=sum(br, a[i]); } return br; } const int maxn=2505, Log=12, pot=(1<<Log); const int inf=1e9; struct tmin{ int t[pot*2]; tmin(){ for(int i=0; i<pot*2; i++){ t[i]=inf; } } void update(int x, int val){ t[x]=val; for(x/=2; x>0; x/=2){ t[x]=min(t[x*2], t[x*2+1]); } } int query(int L, int D, int x, int l, int d){ if(L>=l && D<=d){ return t[x]; } int lijeva=inf, desna=inf; if((L+D)/2>=l){ lijeva=query(L, (L+D)/2, x*2, l, d); } if((L+D)/2+1<=d){ desna=query((L+D)/2+1, D, x*2+1, l, d); } return min(lijeva, desna); } }; struct tmax{ int t[pot*2]; void update(int x, int val){ t[x]=val; for(x/=2; x>0; x/=2){ t[x]=max(t[x*2], t[x*2+1]); } } int query(int L, int D, int x, int l, int d){ if(L>=l && D<=d){ return t[x]; } int lijeva=0, desna=0; if((L+D)/2>=l){ lijeva=query(L, (L+D)/2, x*2, l, d); } if((L+D)/2+1<=d){ desna=query((L+D)/2+1, D, x*2+1, l, d); } return max(lijeva, desna); } }; tmin R1[maxn], C1[maxn]; tmax R2[maxn], C2[maxn]; ll sol; int svi[maxn][maxn][4]; int n, m; map < int, bool > bio; int svi1[maxn][maxn][4]; ll count_rectangles(vector < vector < int > > a){ n=a.size(); m=a[0].size(); vector < pair <int, int > > v; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][2]=0; } else{ svi1[i][j][2]=v.back().second+1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][2]=0; } else{ svi[i][j][2]=v.back().second+1; } v.push_back({a[i][j], j}); } v.clear(); for(int j=m-1; j>-1; j--){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][3]=m-1; } else{ svi1[i][j][3]=v.back().second-1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][3]=m-1; } else{ svi[i][j][3]=v.back().second-1; } v.push_back({a[i][j], j}); } v.clear(); } for(int j=0; j<m; j++){ for(int i=0; i<n; i++){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][0]=0; } else{ svi1[i][j][0]=v.back().second+1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][0]=0; } else{ svi[i][j][0]=v.back().second+1; } v.push_back({a[i][j], i}); } v.clear(); for(int i=n-1; i>-1; i--){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][1]=n-1; } else{ svi1[i][j][1]=v.back().second-1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][1]=n-1; } else{ svi[i][j][1]=v.back().second-1; } v.push_back({a[i][j], i}); } v.clear(); } for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ R1[i].update(j+pot, svi1[i][j][1]); R2[i].update(j+pot, svi1[i][j][0]); C1[j].update(i+pot, svi1[i][j][3]); C2[j].update(i+pot, svi1[i][j][2]); } } int c[4]; int br; // array < int, 4 > b; for(int i=1; i<n-1; i++){ for(int j=1; j<m-1; j++){ for(int k=0; k<4; k++){ c[k]=svi[i][j][k]; } br=pretvori(c); if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1 || bio[br]){ continue; } /* if(i==1 && j==1){ cout << R1[c[1]+1].query(0, pot-1, 1, c[2], c[3]) << endl; }*/ if(c[0]<R2[c[1]+1].query(0, pot-1, 1, c[2], c[3])){ continue; } if(c[1]>R1[c[0]-1].query(0, pot-1, 1, c[2], c[3])){ continue; } if(c[2]<C2[c[3]+1].query(0, pot-1, 1, c[0], c[1])){ continue; } if(c[3]>C1[c[2]-1].query(0, pot-1, 1, c[0], c[1])){ continue; } bio[br]=1; // cout << c[0] << ' '<< c[2] << ' ' << c[1] << ' ' << c[3] << endl; sol++; } } return sol; }
#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...