Submission #943737

#TimeUsernameProblemLanguageResultExecution timeMemory
943737PanndaFish 2 (JOI22_fish2)C++17
60 / 100
4038 ms14424 KiB
#include <bits/stdc++.h> using namespace std; struct Paint { struct Node { int mn, cnt; int lazy = 0; void add(int delta) { mn += delta; lazy += delta; } void merge(Node a, Node b) { mn = min(a.mn, b.mn); cnt = 0; if (a.mn == mn) cnt += a.cnt; if (b.mn == mn) cnt += b.cnt; } }; int n; vector<Node> nodes; Paint(int n) : n(n), nodes(4 * n) { auto dfs = [&](auto self, int idx, int l, int r) -> void { if (l + 1 == r) { nodes[idx].mn = 0; nodes[idx].cnt = 1; } else { int m = (l + r) >> 1; self(self, 2 * idx + 1, l, m); self(self, 2 * idx + 2, m, r); nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]); } }; dfs(dfs, 0, 0, n); } void down(int idx) { nodes[2 * idx + 1].add(nodes[idx].lazy); nodes[2 * idx + 2].add(nodes[idx].lazy); nodes[idx].lazy = 0; } void add(int ql, int qr, int delta) { auto dfs = [&](auto self, int idx, int l, int r) -> void { if (r <= ql || qr <= l) return; if (ql <= l && r <= qr) return nodes[idx].add(delta); down(idx); int m = (l + r) >> 1; self(self, 2 * idx + 1, l, m); self(self, 2 * idx + 2, m, r); nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]); }; dfs(dfs, 0, 0, n); } int countZero(int ql, int qr) { int fetch = 0; auto dfs = [&](auto self, int idx, int l, int r) -> void { if (r <= ql || qr <= l) return; if (ql <= l && r <= qr) { fetch += nodes[idx].mn == 0 ? nodes[idx].cnt : 0; return; } down(idx); int m = (l + r) >> 1; self(self, 2 * idx + 1, l, m); self(self, 2 * idx + 2, m, r); }; dfs(dfs, 0, 0, n); return fetch; } }; struct SegmentWalk { int n; vector<int> mx; SegmentWalk(int n) : n(n), mx(4 * n, 0) {} void set(int i, int val) { auto dfs = [&](auto self, int idx, int l, int r) -> void { if (l + 1 == r) { mx[idx] = val; } else { int m = (l + r) >> 1; if (i < m) self(self, 2 * idx + 1, l, m); else self(self, 2 * idx + 2, m, r); mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]); } }; dfs(dfs, 0, 0, n); } int walk(int ql, int qr, long long bound, bool request_leftmost) { // in [ql, qr), returns the leftmost (rightmost) position with value > 'bound' auto dfs = [&](auto self, int idx, int l, int r) -> int { if (r <= ql || qr <= l || mx[idx] <= bound) return -1; if (ql <= l && r <= qr) { while (l + 1 < r) { int m = (l + r) >> 1; if (request_leftmost) { if (mx[2 * idx + 1] > bound) idx = 2 * idx + 1, r = m; else idx = 2 * idx + 2, l = m; } else { if (mx[2 * idx + 2] > bound) idx = 2 * idx + 2, l = m; else idx = 2 * idx + 1, r = m; } } return l; } int m = (l + r) >> 1; if (request_leftmost) { int get = self(self, 2 * idx + 1, l, m); if (get != -1) return get; return self(self, 2 * idx + 2, m, r); } else { int get = self(self, 2 * idx + 2, m, r); if (get != -1) return get; return self(self, 2 * idx + 1, l, m); } }; return dfs(dfs, 0, 0, n); } }; struct Fenwick { int n; vector<long long> bit; Fenwick(int n) : n(n), bit(n + 1, 0) {} void add(int i, int delta) { for (i++; i <= n; i += i & -i) bit[i] += delta; } long long sum(int i) { long long res = 0; for (; i > 0; i -= i & -i) res += bit[i]; return res; } long long sum(int l, int r) { return sum(r) - sum(l); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // freopen("inp.inp", "r", stdin); // freopen("out.out", "w", stdout); int n; cin >> n; vector<int> a(n); Fenwick fen(n); SegmentWalk segwalk(n); for (int i = 0; i < n; i++) { cin >> a[i]; fen.add(i, a[i]); segwalk.set(i, a[i]); } auto findSaturatedInterval = [&](int ql, int qr, int &l, int &r, long long &sum) -> void { // O(log^2), find the tightest saturated interval (or [l, r)) containing the initial interval [l, r) while (ql < l || r < qr) { long long old_sum = sum; if (ql < l) { int p = segwalk.walk(ql, l, sum, false); if (p == -1) { sum += fen.sum(ql, l); l = ql; } else { sum += fen.sum(p + 1, l); l = p + 1; if (sum >= a[p]) { sum += a[p]; l = p; } } } if (r < qr) { int p = segwalk.walk(r, qr, sum, true); if (p == -1) { sum += fen.sum(r, qr); r = qr; } else { sum += fen.sum(r, p); r = p; if (sum >= a[p]) { sum += a[p]; r = p + 1; } } } if (sum == old_sum) break; } }; auto findAllSaturatedIntervals = [&](int ql, int qr, int i) -> vector<array<int, 2>> { // O(log^2), find all saturated intervals containing i vector<array<int, 2>> res; int l = i, r = i + 1; long long sum = a[i]; while (true) { findSaturatedInterval(ql, qr, l, r, sum); if (l == ql && r == qr) break; res.push_back({l, r}); if (l == ql || (r < qr && a[r] <= a[l - 1])) { sum += a[r]; r = r + 1; } else { sum += a[l - 1]; l = l - 1; } } return res; }; Paint paint(n); SegmentWalk wow(n); vector<vector<int>> why(n); auto erase = [&](int ql, int qr) -> vector<array<int, 2>> { // erases all intervals containing [ql, qr), return the set of deleted intervals vector<array<int, 2>> res; if (ql < 0 || qr > n) return res; while (true) { int l = wow.walk(0, ql + 1, qr - 1, true); if (l == -1) break; int r = why[l].back(); res.push_back({l, r}); paint.add(l, r, -1); why[l].pop_back(); if (why[l].empty()) wow.set(l, 0); else wow.set(l, why[l].back()); } return res; }; auto insert = [&](int l, int r) -> void { if (find(why[l].begin(), why[l].end(), r) != why[l].end()) return; auto it = why[l].begin(); while (it != why[l].end() && *it < r) ++it; why[l].insert(it, r); wow.set(l, why[l].back()); paint.add(l, r, +1); }; for (int i = 0; i < n; i++) { int l = i, r = i + 1; long long sum = a[i]; findSaturatedInterval(0, n, l, r, sum); if (l != 0 || r != n) insert(l, r); } int q; cin >> q; while (q--) { int type; cin >> type; if (type == 1) { int i, x; cin >> i >> x; i--; auto subinsert = [&](int i) -> void { if (i < 0 || i >= n) return; for (auto [l, r] : findAllSaturatedIntervals(0, n, i)) insert(l, r); }; erase(i - 1, i); erase(i, i + 1); erase(i + 1, i + 2); fen.add(i, -a[i] + x); a[i] = x; segwalk.set(i, x); subinsert(i - 1); subinsert(i); subinsert(i + 1); } if (type == 2) { int l, r; cin >> l >> r; l--; vector<array<int, 2>> erase0 = erase(l - 1, l + 1); vector<array<int, 2>> erase1 = erase(r - 1, r + 1); vector<array<int, 2>> erase2 = erase(l, r); vector<array<int, 2>> insert0 = findAllSaturatedIntervals(l, r, l); vector<array<int, 2>> insert1 = findAllSaturatedIntervals(l, r, r - 1); for (auto [l, r] : insert0) paint.add(l, r, +1); for (auto [l, r] : insert1) paint.add(l, r, +1); cout << paint.countZero(l, r) << '\n'; for (auto [l, r] : insert0) paint.add(l, r, -1); for (auto [l, r] : insert1) paint.add(l, r, -1); for (auto [l, r] : erase0) insert(l, r); for (auto [l, r] : erase1) insert(l, r); for (auto [l, r] : erase2) insert(l, r); } } }
#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...