Submission #220176

#TimeUsernameProblemLanguageResultExecution timeMemory
220176VEGAnnRectangles (IOI19_rect)C++14
100 / 100
2765 ms1037560 KiB
#include <bits/stdc++.h> #include "rect.h" #define all(x) x.begin(),x.end() #define PB push_back #define sz(x) ((int)x.size()) #define pii pair<int,int> #define MP make_pair #define ft first #define sd second using namespace std; typedef long long ll; const int N = 2500; const int oo = 2e9; const int PW = 13; vector<int> lst[N][N]; vector<int> qr[N]; stack<int> stk; int n, m, kol = 0, mx, my, Mx, My, up[N][N], down[N][N], spar[2][N][N][PW], po[N]; int fen[N]; ll ans = 0, big = 0; int get(int tp, int i, int l, int r){ int len = r - l + 1; int pw = po[len]; if (tp == 1) return min(spar[tp][i][l][pw], spar[tp][i][r - (1 << pw) + 1][pw]); else return max(spar[tp][i][l][pw], spar[tp][i][r - (1 << pw) + 1][pw]); } void upd(int x, int vl){ for (; x < n; x = (x | (x + 1))) fen[x] += vl; } int sum(int x){ int res = 0; for (; x >= 0; x = (x & (x + 1)) - 1) res += fen[x]; return res; } long long count_rectangles(std::vector<std::vector<int> > a) { n = sz(a); m = sz(a[0]); if (n < 3 || m < 3) return 0; for (int i = 1; i < n - 1; i++){ while (sz(stk)) stk.pop(); stk.push(0); for (int j = 1; j < m; j++){ bool was = 0; while (sz(stk) > 0 && a[i][stk.top()] <= a[i][j]) { if (a[i][stk.top()] == a[i][j]){ if (!was){ was = 1; lst[stk.top() + 1][j - 1].PB(i); } } else lst[stk.top() + 1][j - 1].PB(i); stk.pop(); } if (sz(stk) && !was) lst[stk.top() + 1][j - 1].PB(i); stk.push(j); } } for (int j = 0; j < m; j++){ while (sz(stk)) stk.pop(); stk.push(-1); for (int i = 0; i < n; i++){ while (sz(stk) > 1 && a[stk.top()][j] < a[i][j]) stk.pop(); up[i][j] = stk.top(); stk.push(i); } while (sz(stk)) stk.pop(); stk.push(n); for (int i = n - 1; i >= 0; i--){ while (sz(stk) > 1 && a[stk.top()][j] < a[i][j]) stk.pop(); down[i][j] = stk.top(); stk.push(i); } } po[0] = -1; for (int i = 1; i <= max(n, m); i++) po[i] = po[i >> 1] + 1; for (int i = 1; i < n - 1; i++){ for (int j = 0; j < m; j++){ spar[0][i][j][0] = up[i + 1][j]; spar[1][i][j][0] = down[i - 1][j]; } for (int pw = 1; pw < PW; pw++) for (int j = 0; j + (1 << pw) - 1 < m; j++){ spar[0][i][j][pw] = max(spar[0][i][j][pw - 1], spar[0][i][j + (1 << (pw - 1))][pw - 1]); spar[1][i][j][pw] = min(spar[1][i][j][pw - 1], spar[1][i][j + (1 << (pw - 1))][pw - 1]); } } for (int c1 = 1; c1 < m - 1; c1++) for (int c2 = c1; c2 < m - 1; c2++){ for (int it = 0; it < sz(lst[c1][c2]); ){ int r1 = lst[c1][c2][it]; int j = it + 1; while (j < sz(lst[c1][c2]) && lst[c1][c2][j] - 1 == lst[c1][c2][j - 1]) j++; int i = lst[c1][c2][j - 1] + 1; for (int r2 = r1; r2 < i; r2++){ int bd = min(n - 1, get(1, r2, c1, c2)); qr[r2].PB(-bd); } for (int r2 = r1; r2 < i; r2++) qr[max(get(0, r2, c1, c2), r1 - 1)].PB(r2); for (int r2 = r1 - 1; r2 < i; r2++) { if (sz(qr[r2])) { for (int cr : qr[r2]) if (cr < 0) ans += sum(-cr - 1) - sum(r2 - 1); else upd(cr, 1); qr[r2].clear(); } } for (int r2 = r1; r2 < i; r2++) upd(r2, -1); it = j; } } 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...