제출 #154453

#제출 시각아이디문제언어결과실행 시간메모리
154453crackersamdjamRectangles (IOI19_rect)C++14
100 / 100
3376 ms737556 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse4,popcnt,abm,mmx,tune=native") #include <bits/stdc++.h> const int MM = 2502; int n, m, ans, stl, vecl; int first[MM], last[MM], bit[MM]; std::pair<int, int> st[MM], vec[MM]; std::vector<std::pair<int, int>> hor[MM][MM], vert[MM][MM]; inline void update(int i, int v){ for(; i < MM; i += i&-i) bit[i] += v; } inline int query(int i){ int ret = 0; for(; i; i -= i&-i) ret += bit[i]; return ret; } long long count_rectangles(std::vector<std::vector<int>> a){ n = a.size(), m = a[0].size(); for(int i = 0; i < n; i++){ stl = 0; for(int j = 0; j < m; j++){ //remove duplicates while(stl && st[stl].first < a[i][j]) stl--; first[j] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second; st[++stl] = {a[i][j], j}; } stl = 0; for(int j = m-1; j >= 0; j--){ while(stl && st[stl].first <= a[i][j]) stl--; last[j] = !stl ? -1 : st[stl].second; st[++stl] = {a[i][j], j}; } for(int j = 0; j < m; j++){ if(first[j] == -1 || last[j] == -1) continue; first[j]++, last[j]--; hor[i][first[j]].push_back({last[j], 1}); } } for(int j = 0; j < m; j++){ stl = 0; for(int i = 0; i < n; i++){ //remove duplicates while(stl && st[stl].first < a[i][j]) stl--; first[i] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second; st[++stl] = {a[i][j], i}; } stl = 0; for(int i = n-1; i >= 0; i--){ while(stl && st[stl].first <= a[i][j]) stl--; last[i] = !stl ? -1 : st[stl].second; st[++stl] = {a[i][j], i}; } for(int i = 0; i < n; i++){ if(first[i] == -1 || last[i] == -1) continue; first[i]++, last[i]--; vert[first[i]][j].push_back({last[i], 1}); } } for(int i = n-1; i >= 0; i--){ for(int j = m-1; j >= 0; j--){ //assert(std::is_sorted(hor[i][j].begin(), hor[i][j].end())); //assert(std::is_sorted(vert[i][j].begin(), vert[i][j].end())); int l = 0, r = 0; while(l < vert[i][j].size() && r < vert[i][j+1].size()){ if(vert[i][j][l].first == vert[i][j+1][r].first){ vert[i][j][l].second = vert[i][j+1][r].second+1; l++; } else if(vert[i][j][l].first > vert[i][j+1][r].first) r++; else l++; } l = r = 0; while(l < hor[i][j].size() && r < hor[i+1][j].size()){ if(hor[i][j][l].first == hor[i+1][j][r].first){ hor[i][j][l].second = hor[i+1][j][r].second+1; l++; } else if(hor[i][j][l].first > hor[i+1][j][r].first) r++; else l++; } /* for(auto &x: vert[i][j]) if(vert[i][j+1].count(x.first)) x.second += vert[i][j+1][x.first]; for(auto &x: hor[i][j]){ if(hor[i+1][j].count(x.first)) x.second += hor[i+1][j][x.first]; vec[vecl++] = {x.first-j+1, x.second}; } */ for(int k = 0; k < hor[i][j].size(); k++) vec[k] = hor[i][j][k]; vecl = hor[i][j].size(); sort(vec, vec+vecl, [](const std::pair<int, int> &x, const std::pair<int, int> &y){ return x.second > y.second; }); l = 0; for(int k = vert[i][j].size()-1; k >= 0; k--){ auto &b = vert[i][j][k]; while(l < vecl && b.first-i+1 <= vec[l].second){ update(vec[l++].first-j+1, 1); } ans += query(b.second); } while(l) update(vec[--l].first-j+1, -1); } } return ans; } #ifndef ONLINE_JUDGE int notmain(){ printf("%lld\n", 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; } #endif

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

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < vert[i][j].size() && r < vert[i][j+1].size()){
                   ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:88:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < vert[i][j].size() && r < vert[i][j+1].size()){
                                            ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < hor[i][j].size() && r < hor[i+1][j].size()){
                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:101:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < hor[i][j].size() && r < hor[i+1][j].size()){
                                           ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:123:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = 0; k < hor[i][j].size(); k++)
                            ~~^~~~~~~~~~~~~~~~~~
#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...