제출 #610784

#제출 시각아이디문제언어결과실행 시간메모리
610784lorenzoferrariRectangles (IOI19_rect)C++17
13 / 100
4577 ms277876 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 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; } /**/ void print(comp a) { cerr << "sz: " << a.sz << " ; "; cerr << "ext: "; for (int i = 0; i < 4; ++i) cerr << a.ext[i] << " "; cerr << "\n"; } vector<int> p; vector<comp> cc; int findset(int v) { return (v == -1 || p[v] == v) ? v : p[v] = findset(p[v]); } bool unionset(int a, int b) { a = findset(a); b = findset(b); if (a == b || a == -1 || b == -1) return false; if (cc[a].sz < cc[b].sz) swap(a, b); p[b] = a; // cerr << "union (" << a/m << "," << a%m << "), (" << b/m << "," << b%m << ")\n"; cc[a] = join(cc[a], cc[b]); return true; } LL count_rectangles(vector<vector<int>> a) { n = a.size(); m = a[0].size(); p.assign(n*m, -1); cc.resize(n*m); int mx = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { mx = max(mx, a[i][j]); } vector<vector<array<int, 2>>> v(mx + 1); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { v[a[i][j]].push_back({i, j}); } vector<int> last_time(n*m, -1); auto add_tile = [&](int i, int j) -> void { int id = m*i + j; p[id] = id; cc[id] = comp(i, j); for (auto [dx, dy] : dd) { int nx = i + dx; int ny = j + dy; if (0 > nx || nx >= n || 0 > ny || ny >= m) continue; unionset(m*i+j, m*nx+ny); } }; LL ans = 0; for (int i = 0; i <= mx; ++i) { for (auto [x, y] : v[i]) { add_tile(x, y); } for (auto [x, y] : v[i]) { int id = findset(m*x + y); if (last_time[id] != i) { last_time[id] = i; ans += cc[id].good(); if (cc[id].good()) { print(cc[id]); } } } } return ans; #if 0 if (mx <= 1) { /**/ 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; #endif }
#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...