제출 #154441

#제출 시각아이디문제언어결과실행 시간메모리
154441DormiRectangles (IOI19_rect)C++14
100 / 100
4905 ms781868 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int lli; typedef pair<int,int> pii; typedef pair<lli,lli> pll; void sc(){} template<typename T,typename... Args> void sc(T& a, Args&... args) {cin>>a,sc(args...);} template<typename T> void pr(T a){cout<<a;} template<typename T,typename... Args> void pr(T a, Args... args) {cout<<a<<" ",pr(args...);} template<typename T> void prl(T a){cout<<a<<"\n";} template<typename T,typename... Args> void prl(T a, Args... args) {cout<<a<<" ",prl(args...);} #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) int bit[2505]; int n,m; void update(int loc, int val){ for(;loc<=n;loc+=loc&-loc)bit[loc]+=val; } int sum(int loc){ int ans=0; for(;loc>0;loc-=loc&-loc)ans+=bit[loc]; return ans; } long long count_rectangles(std::vector<std::vector<int>> a){ n=a.size(); m=a[0].size(); vector<pii> rowranges[n][m]; vector<pii> colranges[n][m]; rep(i,0,n){ int preloc[m]; int sufloc[m]; pii deq[m]; int l=0,r=-1; rep(j,0,m){ while(r>=l&&deq[r].second<=a[i][j])r--; if(r>=l)preloc[j]=deq[r].first; else preloc[j]=-1; deq[++r]={j,a[i][j]}; } l=0,r=-1; rep(j,m,0){ while(r>=l&&deq[r].second<=a[i][j])r--; if(r>=l)sufloc[j]=deq[r].first; else sufloc[j]=-1; deq[++r]={j,a[i][j]}; } rep(j,0,m){ if(preloc[j]!=-1&&sufloc[j]!=-1){ while(rowranges[i][preloc[j]+1].size()&&rowranges[i][preloc[j]+1].back().first==sufloc[j]-1)rowranges[i][preloc[j]+1].pop_back(); rowranges[i][preloc[j]+1].push_back({sufloc[j]-1,1}); } } } rep(i,0,m){ int preloc[n]; int sufloc[n]; pii deq[n]; int l=0,r=-1; rep(j,0,n){ while(r>=l&&deq[r].second<=a[j][i])r--; if(r>=l)preloc[j]=deq[r].first; else preloc[j]=-1; deq[++r]={j,a[j][i]}; } l=0,r=-1; rep(j,n,0){ while(r>=l&&deq[r].second<=a[j][i])r--; if(r>=l)sufloc[j]=deq[r].first; else sufloc[j]=-1; deq[++r]={j,a[j][i]}; } rep(j,0,n){ if(preloc[j]!=-1&&sufloc[j]!=-1){ while(colranges[preloc[j]+1][i].size()&&colranges[preloc[j]+1][i].back().first==sufloc[j]-1)colranges[preloc[j]+1][i].pop_back(); colranges[preloc[j]+1][i].push_back({sufloc[j]-1,1}); } } } rep(i,0,m){ rep(j,n-1,0){ int l=0,r=0; while(l<rowranges[j][i].size()&&r<rowranges[j+1][i].size()){ if(rowranges[j][i][l].first==rowranges[j+1][i][r].first){ rowranges[j][i][l].second+=rowranges[j+1][i][r].second; l++; } else if(rowranges[j][i][l].first>rowranges[j+1][i][r].first){ r++; } else l++; } } } rep(i,0,n){ rep(j,m-1,0){ int l=0,r=0; while(l<colranges[i][j].size()&&r<colranges[i][j+1].size()){ if(colranges[i][j][l].first==colranges[i][j+1][r].first){ colranges[i][j][l].second+=colranges[i][j+1][r].second; l++; } else if(colranges[i][j][l].first>colranges[i][j+1][r].first){ r++; } else l++; } } } int cnt=0; rep(i,0,n)rep(j,0,m){ sort(colranges[i][j].begin(),colranges[i][j].end(),[&] (const pii &a, const pii &b) { return a.second < b.second; }); int r=colranges[i][j].size(); rep(k,rowranges[i][j].size(),0){ while(r>0&&colranges[i][j][r-1].second+j-1>=rowranges[i][j][k].first){ r-=1; update(colranges[i][j][r].first+1,1); } cnt+=sum(rowranges[i][j][k].second+i); } rep(k,r,colranges[i][j].size())update(colranges[i][j][k].first+1,-1); } return cnt; } //int main(){ // cin.tie(NULL); // ios_base::sync_with_stdio(false); // prl(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}})); // return 0; //}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:86:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(l<rowranges[j][i].size()&&r<rowranges[j+1][i].size()){
           ~^~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:86:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(l<rowranges[j][i].size()&&r<rowranges[j+1][i].size()){
                                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:101:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(l<colranges[i][j].size()&&r<colranges[i][j+1].size()){
          ~^~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:101:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(l<colranges[i][j].size()&&r<colranges[i][j+1].size()){
                                    ~^~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:17:70: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
                                                              ~~~~~~~~^~~~~~~
rect.cpp:126:3: note: in expansion of macro 'rep'
   rep(k,r,colranges[i][j].size())update(colranges[i][j][k].first+1,-1);
   ^~~
rect.cpp:17:102: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
                                                                                              ~~~~~~~~^~~~~~~
rect.cpp:126:3: note: in expansion of macro 'rep'
   rep(k,r,colranges[i][j].size())update(colranges[i][j][k].first+1,-1);
   ^~~
rect.cpp:17:134: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
                                                                                                                              ~~~~~~~~^~~~~~~
rect.cpp:126:3: note: in expansion of macro 'rep'
   rep(k,r,colranges[i][j].size())update(colranges[i][j][k].first+1,-1);
   ^~~
#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...