oj.uz

Submission #943639

# Submission time Handle Problem Language Result Execution time Memory
943639 2024-03-11T17:14:51 Z Pannda Fish 2 (JOI22_fish2) C++17
13 / 100
 4000 ms 12880 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);

    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);
//    set<array<int, 2>> saturated_intervals;
//    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) {
//            if (!saturated_intervals.count({l, r})) {
//                saturated_intervals.insert({l, r});
//                paint.add(l, r, +1);
//            }
//        }
//    }

    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 ql, qr;
            cin >> ql >> qr;
            ql--;

            Paint paint(n);
            set<array<int, 2>> saturated_intervals;
            for (int i = ql; i < qr; i++) {
                int l = i, r = i + 1;
                long long sum = a[i];
                findSaturatedInterval(ql, qr, l, r, sum);
                if (l != ql || r != qr) {
                    if (!saturated_intervals.count({l, r})) {
                        saturated_intervals.insert({l, r});
                        paint.add(l, r, +1);
                    }
                }
            }

            cout << paint.countZero(ql, qr) << '\n';
        }
    }
}

Compilation message

fish2.cpp: In function 'int main()':
fish2.cpp:199:10: warning: variable 'findAllSaturatedIntervals' set but not used [-Wunused-but-set-variable]
  199 |     auto findAllSaturatedIntervals = [&](int ql, int qr, int i) -> vector<array<int, 2>> { // O(log^2), find all saturated intervals containing i
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 14 ms 348 KB Output is correct
6 Correct 39 ms 376 KB Output is correct
7 Correct 12 ms 348 KB Output is correct
8 Correct 31 ms 348 KB Output is correct
9 Correct 58 ms 348 KB Output is correct
10 Correct 10 ms 348 KB Output is correct
11 Correct 26 ms 512 KB Output is correct
12 Correct 8 ms 344 KB Output is correct
13 Correct 39 ms 488 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 22 ms 516 KB Output is correct
16 Correct 49 ms 348 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 41 ms 488 KB Output is correct
19 Correct 15 ms 520 KB Output is correct
20 Correct 89 ms 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 114 ms 11856 KB Output is correct
3 Correct 107 ms 11396 KB Output is correct
4 Correct 120 ms 11848 KB Output is correct
5 Correct 129 ms 11328 KB Output is correct
6 Correct 70 ms 9808 KB Output is correct
7 Correct 116 ms 9040 KB Output is correct
8 Correct 70 ms 9816 KB Output is correct
9 Correct 113 ms 8968 KB Output is correct
10 Correct 101 ms 9556 KB Output is correct
11 Correct 97 ms 9556 KB Output is correct
12 Correct 86 ms 9472 KB Output is correct
13 Correct 90 ms 9556 KB Output is correct
14 Correct 80 ms 10836 KB Output is correct
15 Correct 85 ms 10888 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 14 ms 348 KB Output is correct
6 Correct 39 ms 376 KB Output is correct
7 Correct 12 ms 348 KB Output is correct
8 Correct 31 ms 348 KB Output is correct
9 Correct 58 ms 348 KB Output is correct
10 Correct 10 ms 348 KB Output is correct
11 Correct 26 ms 512 KB Output is correct
12 Correct 8 ms 344 KB Output is correct
13 Correct 39 ms 488 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 22 ms 516 KB Output is correct
16 Correct 49 ms 348 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 41 ms 488 KB Output is correct
19 Correct 15 ms 520 KB Output is correct
20 Correct 89 ms 500 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 114 ms 11856 KB Output is correct
23 Correct 107 ms 11396 KB Output is correct
24 Correct 120 ms 11848 KB Output is correct
25 Correct 129 ms 11328 KB Output is correct
26 Correct 70 ms 9808 KB Output is correct
27 Correct 116 ms 9040 KB Output is correct
28 Correct 70 ms 9816 KB Output is correct
29 Correct 113 ms 8968 KB Output is correct
30 Correct 101 ms 9556 KB Output is correct
31 Correct 97 ms 9556 KB Output is correct
32 Correct 86 ms 9472 KB Output is correct
33 Correct 90 ms 9556 KB Output is correct
34 Correct 80 ms 10836 KB Output is correct
35 Correct 85 ms 10888 KB Output is correct
36 Execution timed out 4019 ms 12880 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 114 ms 11856 KB Output is correct
3 Correct 107 ms 11396 KB Output is correct
4 Correct 120 ms 11848 KB Output is correct
5 Correct 129 ms 11328 KB Output is correct
6 Correct 70 ms 9808 KB Output is correct
7 Correct 116 ms 9040 KB Output is correct
8 Correct 70 ms 9816 KB Output is correct
9 Correct 113 ms 8968 KB Output is correct
10 Correct 101 ms 9556 KB Output is correct
11 Correct 97 ms 9556 KB Output is correct
12 Correct 86 ms 9472 KB Output is correct
13 Correct 90 ms 9556 KB Output is correct
14 Correct 80 ms 10836 KB Output is correct
15 Correct 85 ms 10888 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Execution timed out 4098 ms 11572 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 114 ms 11856 KB Output is correct
3 Correct 107 ms 11396 KB Output is correct
4 Correct 120 ms 11848 KB Output is correct
5 Correct 129 ms 11328 KB Output is correct
6 Correct 70 ms 9808 KB Output is correct
7 Correct 116 ms 9040 KB Output is correct
8 Correct 70 ms 9816 KB Output is correct
9 Correct 113 ms 8968 KB Output is correct
10 Correct 101 ms 9556 KB Output is correct
11 Correct 97 ms 9556 KB Output is correct
12 Correct 86 ms 9472 KB Output is correct
13 Correct 90 ms 9556 KB Output is correct
14 Correct 80 ms 10836 KB Output is correct
15 Correct 85 ms 10888 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Execution timed out 4082 ms 11936 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 14 ms 348 KB Output is correct
6 Correct 39 ms 376 KB Output is correct
7 Correct 12 ms 348 KB Output is correct
8 Correct 31 ms 348 KB Output is correct
9 Correct 58 ms 348 KB Output is correct
10 Correct 10 ms 348 KB Output is correct
11 Correct 26 ms 512 KB Output is correct
12 Correct 8 ms 344 KB Output is correct
13 Correct 39 ms 488 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 22 ms 516 KB Output is correct
16 Correct 49 ms 348 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 41 ms 488 KB Output is correct
19 Correct 15 ms 520 KB Output is correct
20 Correct 89 ms 500 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 114 ms 11856 KB Output is correct
23 Correct 107 ms 11396 KB Output is correct
24 Correct 120 ms 11848 KB Output is correct
25 Correct 129 ms 11328 KB Output is correct
26 Correct 70 ms 9808 KB Output is correct
27 Correct 116 ms 9040 KB Output is correct
28 Correct 70 ms 9816 KB Output is correct
29 Correct 113 ms 8968 KB Output is correct
30 Correct 101 ms 9556 KB Output is correct
31 Correct 97 ms 9556 KB Output is correct
32 Correct 86 ms 9472 KB Output is correct
33 Correct 90 ms 9556 KB Output is correct
34 Correct 80 ms 10836 KB Output is correct
35 Correct 85 ms 10888 KB Output is correct
36 Execution timed out 4019 ms 12880 KB Time limit exceeded
37 Halted 0 ms 0 KB -