제출 #844766

#제출 시각아이디문제언어결과실행 시간메모리
844766garyyeRectangles (IOI19_rect)C++17
100 / 100
2839 ms542324 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) typedef pair<int, int> i2; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; const int N = 2505; vector<int> C[N][N]; int L[N][N], R[N][N]; set<int> S[N]; long long count_rectangles(vvi A) { int n = SZ(A), m = SZ(A[0]); auto fun = [](vector<int> a) { vector<i2> ans; int s = SZ(a); vector<int> p(s), l(s, -1), r(s, -1); for (int i = 0; i < s; ++i) p[i] = i; sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; }); for (int i : p) { i2 x = {i, i}; if (i > 0 && l[i - 1] != -1) x.fi = l[i - 1]; if (i + 1 < s && r[i + 1] != -1) x.se = r[i + 1]; if (x.fi > 0 && x.se + 1 < s && min(a[x.fi - 1], a[x.se + 1]) > a[i]) { ans.push_back(x); } r[x.fi] = x.se; l[x.se] = x.fi; } return ans; }; for (int j = 0; j < m; ++j) { vector<int> col(n); for (int i = 0; i < n; ++i) col[i] = A[i][j]; auto pp = fun(col); for (auto& [i1, i2] : pp) { C[i2][j].push_back(i1); } } ll ans = 0; for (int i = 0; i < n; ++i) { vector<int> p(m), l(m, -1), r(m, -1); for (int j = 0; j < m; ++j) p[j] = j, S[j].clear(); sort(p.begin(), p.end(), [&](int l, int r) -> bool { return A[i][l] < A[i][r]; }); for (int j : p) { i2 x = {j, j}; set<int> cur(ALL(C[i][j])); set<int> del; auto inspect = [&](set<int>& s) { for (int c : cur) if (!s.count(c)) del.insert(c); }; if (j > 0 && l[j - 1] != -1) { x.fi = l[j - 1]; inspect(S[x.fi]); } if (j + 1 < m && r[j + 1] != -1) { x.se = r[j + 1]; inspect(S[l[x.se]]); } for (int x : del) cur.erase(x); if (x.fi > 0 && x.se + 1 < m && min(A[i][x.fi - 1], A[i][x.se + 1]) > A[i][j]) { if (i - R[x.fi][x.se] > 1) { L[x.fi][x.se] = i; } R[x.fi][x.se] = i; for (int i1 : cur) { if (i1 >= L[x.fi][x.se]) { ans++; } } } r[x.fi] = x.se; l[x.se] = x.fi; S[x.fi] = cur; } } 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...