oj.uz

Submission #600869

# Submission time Handle Problem Language Result Execution time Memory
600869 2022-07-21T08:40:04 Z KoD Fish 2 (JOI22_fish2) C++17
31 / 100
 666 ms 21508 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) {
                    sum += A[k];   
                    k = seq.upb_to_right(k + 1, sum);
                    if (k == -1) {
                        break;
                    }
                    right.emplace_back(k, seq.sum(i + 1, k));
                } 
            }
            {
                int k = i - 1;
                ll sum = 0;
                while (k >= 0) {
                    sum += A[k];   
                    k = seq.upb_to_left(k, sum);
                    if (k == -1) {
                        break;
                    }
                    left.emplace_back(k, seq.sum(k + 1, i));
                } 
            }
            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 Incorrect 0 ms 212 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 1 ms 212 KB Output is correct
2 Correct 52 ms 15272 KB Output is correct
3 Correct 46 ms 15328 KB Output is correct
4 Correct 57 ms 15272 KB Output is correct
5 Correct 51 ms 15396 KB Output is correct
6 Correct 63 ms 15596 KB Output is correct
7 Correct 27 ms 15036 KB Output is correct
8 Correct 54 ms 15564 KB Output is correct
9 Correct 28 ms 15132 KB Output is correct
10 Correct 47 ms 15592 KB Output is correct
11 Correct 42 ms 15544 KB Output is correct
12 Correct 33 ms 15460 KB Output is correct
13 Correct 31 ms 15420 KB Output is correct
14 Correct 46 ms 15936 KB Output is correct
15 Correct 49 ms 15932 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 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 52 ms 15272 KB Output is correct
3 Correct 46 ms 15328 KB Output is correct
4 Correct 57 ms 15272 KB Output is correct
5 Correct 51 ms 15396 KB Output is correct
6 Correct 63 ms 15596 KB Output is correct
7 Correct 27 ms 15036 KB Output is correct
8 Correct 54 ms 15564 KB Output is correct
9 Correct 28 ms 15132 KB Output is correct
10 Correct 47 ms 15592 KB Output is correct
11 Correct 42 ms 15544 KB Output is correct
12 Correct 33 ms 15460 KB Output is correct
13 Correct 31 ms 15420 KB Output is correct
14 Correct 46 ms 15936 KB Output is correct
15 Correct 49 ms 15932 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 514 ms 15316 KB Output is correct
18 Correct 381 ms 15308 KB Output is correct
19 Correct 458 ms 15436 KB Output is correct
20 Correct 562 ms 15408 KB Output is correct
21 Correct 439 ms 15444 KB Output is correct
22 Correct 346 ms 15308 KB Output is correct
23 Correct 443 ms 15320 KB Output is correct
24 Correct 504 ms 15436 KB Output is correct
25 Correct 516 ms 15436 KB Output is correct
26 Correct 492 ms 15480 KB Output is correct
27 Correct 335 ms 15536 KB Output is correct
28 Correct 329 ms 15516 KB Output is correct
29 Correct 379 ms 15528 KB Output is correct
30 Correct 548 ms 15060 KB Output is correct
31 Correct 582 ms 15052 KB Output is correct
32 Correct 623 ms 15564 KB Output is correct
33 Correct 376 ms 15572 KB Output is correct
34 Correct 584 ms 15416 KB Output is correct
35 Correct 459 ms 15032 KB Output is correct
36 Correct 380 ms 15820 KB Output is correct
37 Correct 345 ms 15452 KB Output is correct
38 Correct 341 ms 15444 KB Output is correct
39 Correct 320 ms 15948 KB Output is correct
40 Correct 316 ms 15932 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 52 ms 15272 KB Output is correct
3 Correct 46 ms 15328 KB Output is correct
4 Correct 57 ms 15272 KB Output is correct
5 Correct 51 ms 15396 KB Output is correct
6 Correct 63 ms 15596 KB Output is correct
7 Correct 27 ms 15036 KB Output is correct
8 Correct 54 ms 15564 KB Output is correct
9 Correct 28 ms 15132 KB Output is correct
10 Correct 47 ms 15592 KB Output is correct
11 Correct 42 ms 15544 KB Output is correct
12 Correct 33 ms 15460 KB Output is correct
13 Correct 31 ms 15420 KB Output is correct
14 Correct 46 ms 15936 KB Output is correct
15 Correct 49 ms 15932 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 666 ms 21508 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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