제출 #223000

#제출 시각아이디문제언어결과실행 시간메모리
223000abekerRectangles (IOI19_rect)C++17
72 / 100
5102 ms1004328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <short, short> pii; const int MAXN = 2.5e3 + 5; class Fenwick { int n; int f[MAXN]; public: Fenwick(int _n) { n = _n; for (int i = 0; i <= n; i++) f[i] = 0; } Fenwick(){} void update(int x, int val) { for (x++; x <= n; x += x & -x) f[x] += val; } int get(int x) { int res = 0; for (x++; x; x -= x & -x) res += f[x]; return res; } int query(int l, int r) { return get(r) - get(l - 1); } }; short foo[MAXN]; vector <short> rows[MAXN][MAXN], cols[MAXN][MAXN]; vector <pii> in[MAXN][MAXN], out[MAXN][MAXN]; Fenwick loga[MAXN]; void find_pairs(const vector <int> &arr, vector <short> ref[MAXN][MAXN], int idx) { int n = arr.size(), sz = 0; for (int i = 0; i < n; i++) { while (sz && arr[foo[sz - 1]] < arr[i]) sz--; if (sz && foo[sz - 1] < i - 1) ref[foo[sz - 1]][i].push_back(idx); foo[sz++] = i; } sz = 0; for (int i = n - 1; i >= 0; i--) { while (sz && arr[foo[sz - 1]] < arr[i]) sz--; if (sz && arr[foo[sz - 1]] > arr[i] && foo[sz - 1] > i + 1) ref[i][foo[sz - 1]].push_back(idx); foo[sz++] = i; } } ll count_rectangles(vector <vector <int>> a) { int N = a.size(); int M = a[0].size(); for (int i = 0; i < N; i++) find_pairs(a[i], rows, i); for (int j = 0; j < M; j++) { vector <int> curr; for (int i = 0; i < N; i++) curr.push_back(a[i][j]); find_pairs(curr, cols, j); } for (int i = 0; i < N; i++) for (int j = i + 2; j < N; j++) { int lst = 0; int sz = cols[i][j].size(); for (int k = 0; k < sz; k++) if (k == sz - 1 || cols[i][j][k + 1] > cols[i][j][k] + 1) { int lo = max(cols[i][j][lst] - 1, 0); int hi = min(cols[i][j][k] + 1, M - 1); for (int l = lo; l <= hi; l++) { in[l][lo].push_back({i, j}); out[l][hi].push_back({i, j}); } lst = k + 1; } } ll sol = 0; for (int i = 0; i < N; i++) loga[i] = Fenwick(N); for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) { for (auto it : in[i][j]) loga[it.first].update(it.second, 1); if (j > i + 1) { int lst = 0; int sz = rows[i][j].size(); for (int k = 0; k < sz; k++) if (k == sz - 1 || rows[i][j][k + 1] > rows[i][j][k] + 1) { int lo = max(rows[i][j][lst] - 1, 0); int hi = min(rows[i][j][k] + 1, N - 1); for (int l = lo; l <= hi; l++) sol += loga[l].query(lo, hi); lst = k + 1; } } for (auto it : out[i][j]) loga[it.first].update(it.second, -1); } return sol; }
#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...