Submission #1034423

#TimeUsernameProblemLanguageResultExecution timeMemory
1034423amirhoseinfar1385Rectangles (IOI19_rect)C++17
0 / 100
287 ms593092 KiB
#include "rect.h" #include<bits/stdc++.h> using namespace std; const long long maxn=2500+10,ted=8; long long all[maxn][maxn],vis[maxn][maxn],tp[maxn][maxn],n,m,dpp[maxn][maxn],dpd[maxn][maxn]; vector<long long>alll[maxn][maxn],alld[maxn][maxn]; vector<pair<long long,pair<long long,long long>>>allq[maxn][maxn]; vector<pair<long long,long long>>addy[maxn][maxn]; long long mainres=0; struct fenwick{ long long fn[maxn]; vector<long long>allind; void clear(){ for(auto x:allind){ while(x<maxn){ fn[x]=0; x+=((-x)&x); } } allind.clear(); } void add(long long i,long long w){ i++; allind.push_back(i); while(i<maxn){ fn[i]+=w; i+=((-i)&i); } } long long pors(long long l,long long r){ long long ret=0; r++; while(l>0){ ret-=fn[l]; l-=((-l)&l); } while(r>0){ ret+=fn[r]; r-=((-r)&r); } return ret; } }fen; void pre(){ for(long long i=1;i<=n;i++){ vector<pair<long long,long long>>allv; for(long long j=1;j<=m;j++){ while((long long)allv.size()>0&&allv.back().first<all[i][j]){ alll[i][j].push_back(allv.back().second); allv.pop_back(); } if((long long)allv.size()>0){ alll[i][j].push_back(allv.back().second); } allv.push_back(make_pair(all[i][j],j)); } } for(long long j=1;j<=m;j++){ vector<pair<long long,long long>>allv; for(long long i=n;i>=1;i--){ while((long long)allv.size()>0&&allv.back().first<all[i][j]){ alld[i][j].push_back(allv.back().second); allv.pop_back(); } if((long long)allv.size()>0){ alld[i][j].push_back(allv.back().second); } allv.push_back(make_pair(all[i][j],i)); } } } void solveq(){ for(long long i=1;i<=n;i++){ for(long long j=1;j<=m;j++){ sort(addy[i][j].begin(),addy[i][j].end()); sort(allq[i][j].begin(),allq[i][j].end()); // cout<<i<<" "<<j<<" :"<<endl; // for(auto x:addy[i][j]){ // cout<<x.first<<" "<<x.second<<endl; // } // for(auto x:allq[i][j]){ // cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<endl; // } while((long long)addy[i][j].size()>0&&(long long)allq[i][j].size()>0){ if(addy[i][j].back().first>=allq[i][j].back().first){ fen.add(addy[i][j].back().second,1); addy[i][j].pop_back(); }else{ mainres+=fen.pors(allq[i][j].back().second.first,allq[i][j].back().second.second); allq[i][j].pop_back(); } } while((long long)allq[i][j].size()>0){ mainres+=fen.pors(allq[i][j].back().second.first,allq[i][j].back().second.second); allq[i][j].pop_back(); } fen.clear(); } } } void calq(){ for(long long i=0;i<=n;i++){ for(long long j=1;j<=m;j++){ for(auto x:alld[i][j]){ if(x<=i+1){ continue; } dpp[x][j]=dpp[x][j-1]+1; allq[i+1][j+1].push_back(make_pair((x-i-1),make_pair(j-dpp[x][j],j-1))); } } for(long long j=1;j<=m;j++){ for(auto x:alld[i][j]){ if(x<=i+1){ continue; } dpp[x][j]=0; } } } for(long long j=1;j<=m;j++){ for(long long i=n;i>=1;i--){ for(auto x:alll[i][j]){ if(x+1>=j){ continue; } dpp[i][x]=dpp[i+1][x]+1; addy[i][j].push_back(make_pair(dpp[i][x],x)); } } for(long long i=n;i>=1;i--){ for(auto x:alll[i][j]){ if(x+1>=j){ continue; } dpp[i][x]=0; } } } } void solve(){ pre(); calq(); solveq(); } long long count_rectangles(std::vector<std::vector<int> > a) { n=a.size(); m=a[0].size(); for(long long i=1;i<=n;i++){ for(long long j=1;j<=m;j++){ all[i][j]=a[i-1][j-1]; } } solve(); return mainres; }
#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...