oj.uz

Submission #943722

# Submission time Handle Problem Language Result Execution time Memory
943722 2024-03-11T18:40:56 Z Pannda Fish 2 (JOI22_fish2) C++17
8 / 100
 118 ms 18064 KB 
#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<set<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;
        while (true) {
            int l = wow.walk(0, ql, qr - 1, true);
            if (l == -1) break;
            int r = *why[l].rbegin();
            paint.add(l, r, -1);
            res.push_back({l, r});
            why[l].erase(r);
            if (why[l].empty()) wow.set(l, 0);
            else wow.set(l, *why[l].rbegin());
        }
        return res;
    };

    auto insert = [&](int l, int r) -> void {
        if (why[l].count(r)) return;
        why[l].insert(r);
        wow.set(l, *why[l].rbegin());
        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, i + 1);
            erase(i - 1, i);
            erase(i + 1, i + 2);
            fen.add(i, -a[i] + x);
            a[i] = x;
            segwalk.set(i, x);
            subinsert(i);
            subinsert(i - 1);
            subinsert(i + 1);
        }
        if (type == 2) {
            int l, r;
            cin >> l >> r;
            l--;

            // assumes l = 0 and r = n (subtask 5)
            cout << max(1, paint.countZero(0, n)) << '\n';
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 110 ms 18064 KB Output is correct
3 Correct 112 ms 17540 KB Output is correct
4 Correct 111 ms 18004 KB Output is correct
5 Correct 108 ms 17488 KB Output is correct
6 Correct 70 ms 15952 KB Output is correct
7 Correct 118 ms 15500 KB Output is correct
8 Correct 70 ms 15956 KB Output is correct
9 Correct 111 ms 15164 KB Output is correct
10 Correct 98 ms 15836 KB Output is correct
11 Correct 91 ms 15764 KB Output is correct
12 Correct 84 ms 15956 KB Output is correct
13 Correct 87 ms 15956 KB Output is correct
14 Correct 85 ms 17288 KB Output is correct
15 Correct 87 ms 17232 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 110 ms 18064 KB Output is correct
3 Correct 112 ms 17540 KB Output is correct
4 Correct 111 ms 18004 KB Output is correct
5 Correct 108 ms 17488 KB Output is correct
6 Correct 70 ms 15952 KB Output is correct
7 Correct 118 ms 15500 KB Output is correct
8 Correct 70 ms 15956 KB Output is correct
9 Correct 111 ms 15164 KB Output is correct
10 Correct 98 ms 15836 KB Output is correct
11 Correct 91 ms 15764 KB Output is correct
12 Correct 84 ms 15956 KB Output is correct
13 Correct 87 ms 15956 KB Output is correct
14 Correct 85 ms 17288 KB Output is correct
15 Correct 87 ms 17232 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 110 ms 18064 KB Output is correct
3 Correct 112 ms 17540 KB Output is correct
4 Correct 111 ms 18004 KB Output is correct
5 Correct 108 ms 17488 KB Output is correct
6 Correct 70 ms 15952 KB Output is correct
7 Correct 118 ms 15500 KB Output is correct
8 Correct 70 ms 15956 KB Output is correct
9 Correct 111 ms 15164 KB Output is correct
10 Correct 98 ms 15836 KB Output is correct
11 Correct 91 ms 15764 KB Output is correct
12 Correct 84 ms 15956 KB Output is correct
13 Correct 87 ms 15956 KB Output is correct
14 Correct 85 ms 17288 KB Output is correct
15 Correct 87 ms 17232 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -