Submission #610770

#TimeUsernameProblemLanguageResultExecution timeMemory
610770lorenzoferrariRectangles (IOI19_rect)C++17
50 / 100
5020 ms50336 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; using LL = long long; #define UP 0 #define LEFT 1 #define DOWN 2 #define RIGHT 3 vector<int> next_geq_val(vector<int> v) { int n = v.size(); stack<pair<int, int>> st; st.push({1e9, n}); vector<int> ans(n); for (int i = n-1; i >= 0; --i) { while (st.top().first < v[i]) st.pop(); ans[i] = st.top().second; st.push({v[i], i}); } return ans; } vector<int> prev_geq_val(vector<int> v) { int n = v.size(); reverse(v.begin(), v.end()); auto r = next_geq_val(v); reverse(r.begin(), r.end()); for (int& i : r) { i = n - 1 - i; } return r; } int n, m; /**/ constexpr int INF = 1e9; const vector<array<int, 2>> dd{{0,1},{0,-1},{1,0},{-1,0}}; struct comp { int sz; array<int, 4> ext; comp() : sz(0), ext({INF, INF, -INF, -INF}) {} comp(int i, int j) : sz(1), ext({i,j,i,j}) {} bool good() { if (ext[UP] == 0 || ext[DOWN] == n-1) return false; if (ext[LEFT] == 0 || ext[RIGHT] == m-1) return false; return sz == (ext[DOWN] - ext[UP] + 1) * (ext[RIGHT] - ext[LEFT] + 1); } }; comp join(const comp& a, const comp& b) { comp ans; ans.sz = a.sz + b.sz; ans.ext[UP] = min(a.ext[UP], b.ext[UP]); ans.ext[LEFT] = min(a.ext[LEFT], b.ext[LEFT]); ans.ext[DOWN] = max(a.ext[DOWN], b.ext[DOWN]); ans.ext[RIGHT] = max(a.ext[RIGHT], b.ext[RIGHT]); return ans; } /**/ LL count_rectangles(vector<vector<int>> a) { n = a.size(); m = a[0].size(); int mx = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { mx = max(mx, a[i][j]); } if (mx <= 1) { /**/ LL ans = 0; vector<vector<bool>> vis(n, vector<bool>(m, false)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (vis[i][j] || a[i][j] == 1) continue; comp cur(i, j); queue<array<int, 2>> Q; Q.push({i, j}); vis[i][j] = true; while (!Q.empty()) { auto [x, y] = Q.front(); Q.pop(); for (auto [dx, dy] : dd) { int nx = x + dx; int ny = y + dy; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (vis[nx][ny] || a[nx][ny] == 1) continue; vis[nx][ny] = true; Q.push({nx, ny}); cur = join(cur, comp(nx, ny)); } } ans += cur.good(); } return ans; /**/ } vector<vector<array<int, 4>>> ext(n, vector<array<int, 4>>(m)); // LEFT & RIGHT for (int i = 0; i < n; ++i) { auto v = a[i]; auto nxt = next_geq_val(v); auto prv = prev_geq_val(v); for (int j = 0; j < m; ++j) { ext[i][j][LEFT] = prv[j]; ext[i][j][RIGHT] = nxt[j]; } } // UP & DOWN for (int j = 0; j < m; ++j) { vector<int> v(n); for (int i = 0; i < n; ++i) v[i] = a[i][j]; auto nxt = next_geq_val(v); auto prv = prev_geq_val(v); for (int i = 0; i < n; ++i) { ext[i][j][UP] = prv[i]; ext[i][j][DOWN] = nxt[i]; } } LL ans = 0; for (int r = 0; r < n; ++r) for (int c = 0; c < m; ++c) { int rwall = m-1; for (int rr = r+2; rr < n; ++rr) { rwall = min(rwall, ext[rr-1][c][RIGHT]); int dwall = n-1; for (int cc = c+2; cc <= rwall; ++cc) { dwall = min(dwall, ext[r][cc-1][DOWN]); if (rr > dwall) break; bool works = true; // orizzontali for (int j = c+1; works && j < cc; ++j) { // works &= (ext[r][j][DOWN] >= rr); works &= (ext[rr][j][UP] <= r); } // verticali for (int i = r+1; works && i < rr; ++i) { // works &= (ext[i][c][RIGHT] >= cc); works &= (ext[i][cc][LEFT] <= c); } ans += works; } } } return ans; }
#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...