제출 #569612

#제출 시각아이디문제언어결과실행 시간메모리
569612ngpin04Rectangles (IOI19_rect)C++17
0 / 100
237 ms452864 KiB
#include "rect.h" #include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 2505; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); vector <pair <int, int>> sr[N][N], sc[N][N]; vector <pair <int, int>> events[N]; vector <int> col[N][N]; int pos[N][N]; int lim[N][N]; int a[N][N]; int v[N]; int l[N]; int r[N]; int n,m; void findmax(int a[], int l[], int n) { vector <int> s; s.push_back(0); a[0] = oo; for (int i = 1; i <= n; i++) { while (a[i] > a[s.back()]) s.pop_back(); l[i] = s.back(); s.push_back(i); } } void addrow(int i, int u, int v) { if (sr[u][v].size() && sr[u][v].back().se == i - 1) sr[u][v].back().se = i; else sr[u][v].push_back(mp(i, i)); } void addcol(int j, int u, int v) { if (sc[u][v].size() && sc[u][v].back().se == j - 1) sc[u][v].back().se = j; else sc[u][v].push_back(mp(j, j)); col[u][j].push_back(v); } void build() { for (int i = 1; i <= n; i++) { findmax(a[i], l, m); reverse(a[i] + 1, a[i] + m + 1); findmax(a[i], r, m); reverse(a[i] + 1, a[i] + m + 1); reverse(r + 1, r + m + 1); for (int j = 1; j <= m; j++) r[j] = (m - r[j] + 1); for (int j = 1; j <= m; j++) { if (l[j] > 0 && l[j] != j - 1) { auto [u, v] = mp(l[j], j); addrow(i, u, v); } if (r[j] <= m && r[j] != j + 1 && a[i][j] < a[i][r[j]]) { auto [u, v] = mp(j, r[j]); addrow(i, u, v); } } } for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) v[i] = a[i][j]; findmax(v, l, n); reverse(v + 1, v + n + 1); findmax(v, r, n); reverse(r + 1, r + n + 1); for (int i = 1; i <= n; i++) r[i] = (n - r[i] + 1); for (int i = 1; i <= n; i++) { if (l[i] > 0 && l[i] != i - 1) { auto [u, v] = mp(l[i], i); addcol(j, u, v); } if (r[i] <= n && r[i] != i + 1 && a[i][j] < a[r[i]][j]) { auto [u, v] = mp(i, r[i]); addcol(j, u, v); } } } for (int l = 1; l <= m; l++) for (int r = l + 1; r <= m; r++) for (auto [u, v] : sr[l][r]) { events[u].push_back({l, r}); events[v + 1].push_back({-l, -r}); } } int solve() { build(); int res = 0; vector <pair <int, int>> cand; for (int i = 1; i < n; i++) { for (auto [l, r] : events[i]) { if (l > 0) { pos[l][r] = cand.size(); cand.push_back({l, r}); } else { l = -l, r = -r; pos[cand.back().fi][cand.back().se] = pos[l][r]; swap(cand[pos[l][r]], cand.back()); cand.pop_back(); } } for (auto [l, r] : cand) { pair <int, int> tmp = {i, oo}; int j = prev(upper_bound(ALL(sr[l][r]), tmp))->se; // cerr << i << " " << j << " " << l << " " << r << "\n"; for (int k : col[i - 1][l + 1]) if (k <= j + 1) { pair <int, int> tmp = {l + 1, oo}; if (!lim[i - 1][k]) lim[i - 1][k] = prev(upper_bound(ALL(sc[i - 1][k]), tmp))->se; res += lim[i - 1][k] >= r - 1; // cerr << k << " " << lim << "\n"; } } } return res; } long long count_rectangles(vector<vector<int>> _a) { n = _a.size(); m = _a[0].size(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = _a[i - 1][j - 1]; return solve(); } //#include "grader.cpp"
#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...