제출 #1067996

#제출 시각아이디문제언어결과실행 시간메모리
1067996Gromp15Rectangles (IOI19_rect)C++17
0 / 100
12 ms348 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2") #include "rect.h" #define ll long long #define ar array #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rint(l, r) uniform_int_distribution<int>(l, r)(rng) struct fenwick { int n; vector<int> bit; fenwick(int a) : n(a), bit(a+1) {} void update(int pos, int x) { pos++; for (int i = pos; i <= n; i += i&-i) bit[i] += x; } int sum(int pos) { int res = 0; while (pos) res += bit[pos], pos -= pos&-pos; return res; } int query(int l, int r) { return sum(r+1) - sum(l); } }; long long count_rectangles(std::vector<std::vector<int>> a) { int n = sz(a), m = sz(a[0]); vector ok(n, vector(n, vector<bool>(m))); for (int i = 0; i < m; i++) { for (int j = 1; j < n-1; j++) { int mx = 0; for (int k = j; k < n-1; k++) { ckmax(mx, a[k][i]); ok[j][k][i] = mx >= min(a[j-1][i], a[k+1][i]); } } } vector<vector<int>> right(n, vector<int>(m, -1)), left(n, vector<int>(m, m-1)); for (int i = 0; i < n; i++) { for (int j = 1; j < m-1; j++) { int mx = 0; for (int k = j; k < m-1; k++) { ckmax(mx, a[i][k]); if (mx >= a[i][j-1]) break; right[i][j] = k; } } for (int j = m-2; j >= 1; j--) { int mx = 0; for (int k = j; k >= 1; k--) { ckmax(mx, a[i][k]); if (mx >= a[i][j+1]) break; left[i][j] = k; } } } long long ans = 0; for (int i = 1; i < n-1; i++) { vector<int> R(m, m-2), L(m, -1); for (int j = i; j < n-1; j++) { for (int k = 0; k < m; k++) { ckmin(R[k], right[j][k]); ckmax(L[k], left[j][k]); } vector<int> to(m, -1); for (int k = m-1; k >= 0; k--) if (!ok[i][j][k]) { int l = k; while (l && !ok[i][j][l-1]) l--; for (int z = l; z <= k; z++) to[z] = k; k = l; } fenwick fw(m); for (int k = 1; k < m-1; k++) { int r = min(to[k], R[k]); if (r >= k) fw.update(r, 1), fw.update(k-1, -1); if (L[k] <= k) ans += fw.query(L[k], k); } } } 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...