제출 #197758

#제출 시각아이디문제언어결과실행 시간메모리
197758MinnakhmetovRectangles (IOI19_rect)C++14
0 / 100
280 ms295416 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define all(aaa) aaa.begin(), aaa.end() const int N = 2505; int stk[N], to_l[N], to_r[N], w[N], last_v[N][N], last_h[N][N], c_v[N][N], c_h[N][N], t[N]; vector<int> lt[N][N], up[N][N]; pair<int, int> ls[N]; void upd(int x, int y) { for (; x < N; x |= x + 1) t[x] += y; } int que(int x) { int s = 0; for (; x >= 0; x = (x & (x + 1)) - 1) s += t[x]; return s; } void handle(int len) { fill(to_l, to_l + len, -1); fill(to_r, to_r + len, -1); int z = 0; for (int i = 0; i < len; i++) { while (z > 0 && w[stk[z - 1]] <= w[i]) { to_r[stk[--z]] = i; } stk[z++] = i; } z = 0; for (int i = len - 1; i >= 0; i--) { while (z > 0 && w[stk[z - 1]] <= w[i]) { to_l[stk[--z]] = i; } stk[z++] = i; } } ll count_rectangles(vector<vector<int>> a) { int n = a.size(), m = a[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) w[j] = a[i][j]; handle(m); for (int j = 0; j < m; j++) { if (to_l[j] != -1 && to_l[j] + 1 < j) { lt[i][j - 1].push_back(to_l[j] + 1); } if (to_r[j] != -1 && to_l[to_r[j]] != j && j + 1 < to_r[j]) { lt[i][to_r[j] - 1].push_back(j + 1); } } } for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) { w[i] = a[i][j]; } handle(n); for (int i = 0; i < n; i++) { if (to_l[i] != -1 && to_l[i] + 1 < i) { up[i - 1][j].push_back(to_l[i] + 1); } if (to_r[i] != -1 && to_l[to_r[i]] != i && i + 1 < to_r[i]) { up[to_r[i] - 1][j].push_back(i + 1); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { last_v[i][j] = -1; last_h[i][j] = -1; } } ll ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int x : lt[i][j]) { if (last_v[j][x] != i - 1) c_v[j][x] = 0; last_v[j][x] = i; c_v[j][x]++; } for (int x : up[i][j]) { if (last_h[i][x] != j - 1) c_h[i][x] = 0; last_h[i][x] = j; c_h[i][x]++; } if (lt[i][j].empty()) continue; sort(all(lt[i][j])); int p_lt = lt[i][j].size() - 1; int z = 0; for (int x : up[i][j]) { ls[z++] = {j - c_h[i][x] + 1, i}; } sort(ls, ls + z); for (int k = z - 1; k >= 0; k--) { while (p_lt >= 0 && lt[i][j][p_lt] >= ls[k].first) { upd(i - c_v[j][lt[i][j][p_lt]] + 1, 1); p_lt--; } ans += que(ls[k].second); } for (int x : lt[i][j]) { upd(i - c_v[j][lt[i][j][x]] + 1, -1); } } } 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...