Submission #1069039

#TimeUsernameProblemLanguageResultExecution timeMemory
1069039RaresFelixRectangles (IOI19_rect)C++17
72 / 100
5065 ms708492 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using ii = pair<int, int>; vector<pair<ii, ii> > get_linii(vector<vi> &a) { int n = int(a.size()), m = int(a[0].size()); vector<set<ii> > Perechi(n); for(int i = 1; i + 1 < n; ++i) { vector<ii> ord; for(int j = 0; j < m; ++j) ord.push_back({a[i][j], j}); sort(ord.rbegin(), ord.rend()); set<int> Poz; int p2 = 0; for(int j = 0; j < m; ++j) { auto [v, p] = ord[j]; while(p2 < m && ord[p2].first == v) { Poz.insert(ord[p2].second); ++p2; } if(1) { auto it = Poz.lower_bound(p); ++it; if(it != Poz.end()) { if(*it > p + 1) Perechi[i].insert(ii{p, *it}); } } if(1) { auto it = Poz.lower_bound(p); if(it != Poz.begin()) { --it; if(p > *it + 1) Perechi[i].insert(ii{*it, p}); } } } } vector<pair<ii, ii> > Re; for(int i = 0; i < n; ++i) { for(auto it : Perechi[i]) { int p = i; while(p + 1 < n && Perechi[p + 1].count(it)) ++p; Re.push_back({{i - 1, p + 1}, it}); for(int j = i + 1; j <= p; ++j) Perechi[j].erase(it); } } return Re; } ll count_rectangles(vector<vi> a) { int n = int(a.size()), m = int(a[0].size()); vector<vi> b(m, vi(n, 0)); for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) b[j][i] = a[i][j]; auto V = get_linii(a), H = get_linii(b); for(auto &[x, y] : H) swap(x, y); auto inclus = [&](ii a, ii b) { ///b inclus in a return b.first >= a.first && b.second <= a.second; }; int re = 0; vector< vector<vector<ii> > > LinV(n, vector(m, vector<ii>())); auto LinH = LinV; for(auto [x, y] : V) { for(int i = x.first; i <= x.second; ++i) { LinV[i][y.second].push_back({i - x.first, y.second - y.first}); } } for(auto [x, y] : H) { for(int j = y.first; j <= y.second; ++j) { LinH[x.second][j].push_back({x.second - x.first, j - y.first}); } } for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { for(auto [xh, yh] : LinH[i][j]) { for(auto [xv, yv] : LinV[i][j]) { if(xh <= xv & yh >= yv) ++re; } } } } return re; }

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:87:27: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   87 |                     if(xh <= xv & yh >= yv)
      |                        ~~~^~~~~
rect.cpp:66:10: warning: variable 'inclus' set but not used [-Wunused-but-set-variable]
   66 |     auto inclus = [&](ii a, ii b) {
      |          ^~~~~~
#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...