Submission #1256173

#TimeUsernameProblemLanguageResultExecution timeMemory
1256173biankRectangles (IOI19_rect)C++20
50 / 100
5092 ms782500 KiB
#include <bits/stdc++.h> using namespace std; #define forsn(i, s, n) for (int i = int(s); i < int(n); i++) #define forn(i, n) forsn(i, 0, n) #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--) #define dforn(i, n) dforsn(i, 0, n) #define sz(x) int(x.size()) #define all(x) begin(x), end(x) using ii = pair<int, int>; using vi = vector<int>; using ll = long long; using vll = vector<ll>; #define fst first #define snd second #define pb push_back #define eb emplace_back const int INF = 1e9 + 20; struct SparseTable { vector<vi> st; SparseTable() {} SparseTable(vi &a) { int log = 1; while ((1 << log) < sz(a)) log++; st.resize(log); st[0] = a; forn(i, log - 1) { st[i + 1].resize(sz(a), INF); forn(j, sz(a) - (1 << i)) { st[i + 1][j] = max(st[i][j], st[i][j + (1 << i)]); } } } int query(int l, int r) { //[l, r) if (r - l <= 0) return -INF; int log = 31 - __builtin_clz(r - l); return max(st[log][l], st[log][r - (1 << log)]); } }; ll count_rectangles(vector<vi> a) { int n = sz(a), m = sz(a[0]); vector<vi> l(n, vi(m)), r(n, vi(m)); vector<vi> d(n, vi(m)), u(n, vi(m)); forn(i, n) forn(j, m) { int k = j - 1; while (k >= 0 && a[i][k] < a[i][j]) k = l[i][k]; l[i][j] = k; } forn(i, n) dforn(j, m) { int k = j + 1; while (k < m && a[i][k] < a[i][j]) k = r[i][k]; r[i][j] = k; } forn(i, m) forn(j, n) { int k = j - 1; while (k >= 0 && a[k][i] < a[j][i]) k = u[k][i]; u[j][i] = k; } forn(i, m) dforn(j, n) { int k = j + 1; while (k < n && a[k][i] < a[j][i]) k = d[k][i]; d[j][i] = k; } vector<SparseTable> rows(n), columns(m); forn(i, n) rows[i] = SparseTable(a[i]); forn(j, m) { vi v; forn(i, n) v.pb(a[i][j]); columns[j] = SparseTable(v); } vector<tuple<int, int, int, int>> ret; auto check = [&](int i1, int i2, int j1, int j2) { if (i1 < 0 || i2 >= n || j1 < 0 || j2 >= m) return; if (i2 - i1 < 2 || j2 - j1 < 2) return; forsn(i, i1 + 1, i2) { int maxi = rows[i].query(j1 + 1, j2); if (maxi >= a[i][j1] || maxi >= a[i][j2]) return; } forsn(j, j1 + 1, j2) { int maxi = columns[j].query(i1 + 1, i2); if (maxi >= a[i1][j] || maxi >= a[i2][j]) return; } ret.eb(i1, i2, j1, j2); }; forsn(i, 1, n - 1) forsn(j, 1, m - 1) { check(u[i + 1][j], i + 1, j - 1, r[i][j - 1]); check(u[i + 1][j], i + 1, l[i][j + 1], j + 1); check(i - 1, d[i - 1][j], l[i][j + 1], j + 1); check(i - 1, d[i - 1][j], j - 1, r[i][j - 1]); check(i - 1, d[i - 1][j], j - 1, r[d[i - 1][j] - 1][j - 1]); check(i - 1, d[i - 1][j], l[d[i - 1][j] - 1][j + 1], j + 1); } sort(all(ret)); return unique(all(ret)) - begin(ret); }
#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...