Submission #943604

#TimeUsernameProblemLanguageResultExecution timeMemory
943604PanndaFish 2 (JOI22_fish2)C++17
8 / 100
4070 ms8856 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, r, m); }; 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); int n; cin >> n; vector<int> a(n); Fenwick fen(n); SegmentWalk segwalk(n); Paint paint(n); for (int i = 0; i < n; i++) { cin >> a[i]; fen.add(i, a[i]); segwalk.set(i, a[i]); } auto findSaturator = [&](int i) -> array<int, 2> { int l = i, r = i + 1; long long sum = a[i]; while (l > 0 || r < n) { long long old_sum = sum; if (l > 0) { int p = segwalk.walk(0, l, sum, false); if (p == -1) { sum += fen.sum(l); l = 0; } else { sum += fen.sum(p + 1, l); l = p + 1; if (sum >= a[p]) { sum += a[p]; l = p; } } } if (r < n) { int p = segwalk.walk(r, n, sum, true); if (p == -1) { sum += fen.sum(r, n); r = n; } else { sum += fen.sum(r, p); r = p; if (sum >= a[p]) { sum += a[p]; r = p + 1; } } } if (sum == old_sum) break; } return {l, r}; }; int q; cin >> q; while (q--) { int type; cin >> type; if (type == 1) { int i, x; cin >> i >> x; i--; fen.add(i, -a[i] + x); a[i] = x; segwalk.set(i, x); } if (type == 2) { int l, r; cin >> l >> r; l--; // assumes l = 0, r = n; int res = 0; for (int i = 0; i < n; i++) { if (findSaturator(i) == array<int, 2>{0, n}) res++; } cout << res << '\n'; } } }
#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...