oj.uz

Submission #600875

# Submission time Handle Problem Language Result Execution time Memory
600875 2022-07-21T08:42:48 Z KoD Fish 2 (JOI22_fish2) C++17
31 / 100
 850 ms 20580 KB 
#include <bits/stdc++.h>

using ll = long long;
using std::pair;
using std::vector;

class Sequence {
    struct Data {
        int max;
        ll sum;
        static Data identity() {
            return {0, 0};
        }
        static Data make(const int x) {
            return {x, x};
        }
        friend Data operator+(const Data& l, const Data& r) {
            return {std::max(l.max, r.max), l.sum + r.sum};
        }
    };

    int size, logn;
    vector<Data> data;

  public:
    explicit Sequence(const vector<int>& vec) {
        logn = 0;
        while ((1 << logn) < (int)vec.size()) {
            logn += 1;
        }
        size = 1 << logn;
        data.resize(2 * size, Data::identity());
        for (int i = 0; i < (int)vec.size(); ++i) {
            data[size + i] = Data::make(vec[i]);
        }
        for (int i = size - 1; i > 0; --i) {
            data[i] = data[2 * i] + data[2 * i + 1];
        }
    }

    void update(int i, const int x) {
        i += size;
        data[i] = Data::make(x);
        while (i > 1) {
            i >>= 1;
            data[i] = data[2 * i] + data[2 * i + 1];
        }
    }

    ll sum(int l, int r) const {
        l += size;
        r += size;
        ll ret = 0;
        while (l < r) {
            if (l & 1) {
                ret += data[l].sum;
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                ret += data[r].sum;
            }
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }

    int upb_to_right(int l, const ll x) {
        if (l == size) return -1;
        l += size;
        do {
            while (!(l & 1)) l >>= 1;
            if (data[l].max > x) {
                while (l < size) {
                    l <<= 1;
                    if (data[l].max <= x) {
                        l += 1;
                    }
                }
                return l - size;
            }
            l >>= 1;
            l += 1;
        } while (l & (l - 1));
        return -1;
    }

    int upb_to_left(int r, const ll x) {
        if (r == 0) return -1;
        r += size;
        do {
            while (!(r & 1)) r >>= 1;
            r -= 1;
            if (data[r].max > x) {
                while (r < size) {
                    r <<= 1;
                    if (data[r + 1].max > x) {
                        r += 1;
                    }
                }
                return r - size;
            }
            r >>= 1;
        } while (r & (r - 1));
        return -1;
    }
};

class Intervals {
    int size, logn;
    vector<vector<pair<int, int>>> data;

  public:
    explicit Intervals(const int n) {
        logn = 0;
        while ((1 << logn) < n) {
            logn += 1;
        }
        size = 1 << logn;
        data.resize(2 * size);
    }

    void add(const int l, const int r) {
        int i = l + size, j = l + size + 1, k = 1;
        while (j < r) {
            if (!(i & 1)) {
                j += k;
            }
            i >>= 1;
            k <<= 1;
        }
        data[i].emplace_back(l, r);
    }

    template <class F>
    void pop(const int k, const F& f) {
        int i = k + size;
        while (i > 0) {
            while (!data[i].empty()) {
                const auto& [l, r] = data[i].back();
                if (l <= k and k < r) {
                    f(l, r);
                    data[i].pop_back();
                } else {
                    break;
                }
            }
            i >>= 1;
        }
    }
};

class SegmentTree {
    struct Data {
        int min, cnt;
        static Data identity() {
            return {1000000000, 0};
        }
        static Data make(const int x) {
            return {x, 1};
        }
        friend Data operator+(const Data& l, const Data& r) {
            const int m = std::min(l.min, r.min);
            return {m, (l.min == m ? l.cnt : 0) + (r.min == m ? r.cnt : 0)};
        }
    };

    int size, logn;
    vector<Data> data;
    vector<int> add;

    void apply(const int k, const int a) {
        data[k].min += a;
        if (k < size) {
            add[k] += a;
        }
    }
    void flush(const int k) {
        if (add[k] != 0) {
            apply(2 * k, add[k]);
            apply(2 * k + 1, add[k]);
            add[k] = 0;
        }
    }
    void push(const int k) {
        const int lsb = __builtin_ctz(k);
        for (int d = logn; d > lsb; --d) {
            flush(k >> d);
        }
    }

    void fetch(const int k) {
        data[k] = data[2 * k] + data[2 * k + 1];
    }
    void pull(int k) {
        k >>= __builtin_ctz(k);
        while (k > 1) {
            fetch(k >>= 1);
        }
    }

  public:
    explicit SegmentTree(const int n) {
        logn = 0;
        while ((1 << logn) < n) {
            logn += 1;
        }
        size = 1 << logn;
        data.resize(2 * size, Data::identity());
        for (int i = 0; i < n; ++i) {
            data[size + i] = Data::make(0);
        }
        for (int i = size - 1; i > 0; --i) {
            data[i] = data[2 * i] + data[2 * i + 1];
        }
        add.resize(size);
    }

    void operate(int l, int r, const int x) {
        l += size;
        r += size;
        push(l);
        push(r);
        const int lc = l, rc = r;
        while (l < r) {
            if (l & 1) {
                apply(l, x);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                apply(r, x);
            }
            l >>= 1;
            r >>= 1;
        }
        pull(lc);
        pull(rc);
    }

    int fold(int l, int r) {
        l += size;
        r += size;
        push(l);
        push(r);
        Data ret = Data::identity();
        while (l < r) {
            if (l & 1) {
                ret = ret + data[l];
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                ret = data[r] + ret;
            }
            l >>= 1;
            r >>= 1;
        }
        return ret.cnt;
    }
};

int main() {
    int N;
    std::cin >> N;
    vector<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    Sequence seq(A);
    Intervals range(N);
    SegmentTree seg(N);
    const auto insert = [&](int l, int r) {
        if (l + 1 < r) {
            seg.operate(l + 1, r, 1);
            range.add(l, r + 1);
        }
    };
    const auto erase = [&](const int l, const int r) {
        seg.operate(l + 1, r - 1, -1);
    };
    {
        vector<ll> accum(N + 1);
        for (int i = 0; i < N; ++i) {
            accum[i + 1] = accum[i] + A[i];
        }
        vector<int> stack;
        const auto test = [&](const int l, const int r) {
            if (std::min(A[l], A[r]) > accum[r] - accum[l + 1]) {
                insert(l, r);
            }
        };
        for (int i = 0; i < N; ++i) {
            while (!stack.empty() and A[stack.back()] < A[i]) {
                test(stack.back(), i);
                stack.pop_back();
            }
            if (!stack.empty()) {
                test(stack.back(), i);
            }
            stack.push_back(i);
        }
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int i, x;
            std::cin >> i >> x;
            i -= 1;
            A[i] = x;
            seq.update(i, x);
            range.pop(i, erase);
            vector<pair<int, int>> left, right;
            {
                int k = i + 1;
                ll sum = 0;
                while (k < N) {
                    right.emplace_back(k, seq.sum(i + 1, k));
                    sum += A[k];   
                    k = seq.upb_to_right(k + 1, sum);
                    if (k == -1) {
                        break;
                    }
                } 
            }
            {
                int k = i - 1;
                ll sum = 0;
                while (k >= 0) {
                    left.emplace_back(k, seq.sum(k + 1, i));
                    sum += A[k];   
                    k = seq.upb_to_left(k, sum);
                    if (k == -1) {
                        break;
                    }
                } 
            }
            for (const auto& [l, sl] : left) {
                if (std::min(A[i], A[l]) > sl) {
                    insert(l, i);
                }
            }
            for (const auto& [r, sr] : right) {
                if (std::min(A[i], A[r]) > sr) {
                    insert(i, r);
                }
            }
            for (const auto& [l, sl] : left) {
                for (const auto& [r, sr] : right) {
                    if (std::min(A[l], A[r]) > sl + A[i] + sr) {
                        insert(l, r);
                    }
                }
            }
        } else {
            int l, r;
            std::cin >> l >> r;
            l -= 1;
            {
                ll sum = 0;
                const int lc = l;
                int cand = l;
                while (true) {
                    sum += A[l];
                    const int k = seq.upb_to_right(l + 1, sum);
                    if (k == -1 or k >= r) {
                        break;
                    }
                    if (seq.sum(lc, k) < A[k]) {
                        cand = k;
                    }
                    l = k;
                }
                l = cand;
            }
            {
                ll sum = 0;
                const int rc = r;
                int cand = r;
                while (true) {
                    sum += A[r - 1];
                    const int k = seq.upb_to_left(r - 1, sum);
                    if (k == -1 or k < l) {
                        break;
                    }
                    if (seq.sum(k + 1, rc) < A[k]) {
                        cand = k + 1;
                    }
                    r = k + 1;
                }
                r = cand;
            }
            std::cout << seg.fold(l, r) << '\n';
        } 
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 2 ms 300 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 65 ms 15180 KB Output is correct
3 Correct 42 ms 15280 KB Output is correct
4 Correct 63 ms 15160 KB Output is correct
5 Correct 44 ms 15232 KB Output is correct
6 Correct 53 ms 15412 KB Output is correct
7 Correct 28 ms 14896 KB Output is correct
8 Correct 59 ms 15416 KB Output is correct
9 Correct 29 ms 15004 KB Output is correct
10 Correct 45 ms 15436 KB Output is correct
11 Correct 35 ms 15408 KB Output is correct
12 Correct 31 ms 15416 KB Output is correct
13 Correct 31 ms 15360 KB Output is correct
14 Correct 46 ms 15852 KB Output is correct
15 Correct 48 ms 15820 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 2 ms 300 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 65 ms 15180 KB Output is correct
3 Correct 42 ms 15280 KB Output is correct
4 Correct 63 ms 15160 KB Output is correct
5 Correct 44 ms 15232 KB Output is correct
6 Correct 53 ms 15412 KB Output is correct
7 Correct 28 ms 14896 KB Output is correct
8 Correct 59 ms 15416 KB Output is correct
9 Correct 29 ms 15004 KB Output is correct
10 Correct 45 ms 15436 KB Output is correct
11 Correct 35 ms 15408 KB Output is correct
12 Correct 31 ms 15416 KB Output is correct
13 Correct 31 ms 15360 KB Output is correct
14 Correct 46 ms 15852 KB Output is correct
15 Correct 48 ms 15820 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 512 ms 15288 KB Output is correct
18 Correct 370 ms 15160 KB Output is correct
19 Correct 577 ms 15280 KB Output is correct
20 Correct 509 ms 15284 KB Output is correct
21 Correct 488 ms 15280 KB Output is correct
22 Correct 421 ms 15184 KB Output is correct
23 Correct 449 ms 15288 KB Output is correct
24 Correct 540 ms 15400 KB Output is correct
25 Correct 581 ms 15364 KB Output is correct
26 Correct 532 ms 15308 KB Output is correct
27 Correct 336 ms 15436 KB Output is correct
28 Correct 375 ms 15564 KB Output is correct
29 Correct 328 ms 15396 KB Output is correct
30 Correct 608 ms 14932 KB Output is correct
31 Correct 543 ms 14932 KB Output is correct
32 Correct 570 ms 15436 KB Output is correct
33 Correct 418 ms 15448 KB Output is correct
34 Correct 574 ms 15284 KB Output is correct
35 Correct 458 ms 15036 KB Output is correct
36 Correct 436 ms 15668 KB Output is correct
37 Correct 368 ms 15308 KB Output is correct
38 Correct 354 ms 15300 KB Output is correct
39 Correct 359 ms 15840 KB Output is correct
40 Correct 377 ms 15828 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 65 ms 15180 KB Output is correct
3 Correct 42 ms 15280 KB Output is correct
4 Correct 63 ms 15160 KB Output is correct
5 Correct 44 ms 15232 KB Output is correct
6 Correct 53 ms 15412 KB Output is correct
7 Correct 28 ms 14896 KB Output is correct
8 Correct 59 ms 15416 KB Output is correct
9 Correct 29 ms 15004 KB Output is correct
10 Correct 45 ms 15436 KB Output is correct
11 Correct 35 ms 15408 KB Output is correct
12 Correct 31 ms 15416 KB Output is correct
13 Correct 31 ms 15360 KB Output is correct
14 Correct 46 ms 15852 KB Output is correct
15 Correct 48 ms 15820 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 850 ms 20580 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 2 ms 300 KB Output isn't correct
6 Halted 0 ms 0 KB -