oj.uz

답안 #600973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600973 2022-07-21T09:40:12 Z KoD Fish 2 (JOI22_fish2) C++17
31 / 100
 4000 ms 16324 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_rec(int u, int l, int r, int a, int b) {
        const int m = (a + b) / 2;
        if (l <= m and m < r) {
            data[u].emplace_back(l, r);
            return;
        }
        if (r <= m) {
            add_rec(2 * u, l, r, a, m); 
        } else {
            add_rec(2 * u + 1, l, r, m, b); 
        }
    }

    void add(const int l, const int r) {
        add_rec(1, l, r, 0, size);
        // 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) {
        for (auto& vec : data) {
            for (int i = 0; i < (int)vec.size(); ++i) {
                const auto& [l, r] = vec[i];
                if (l <= k and k < r) {
                    f(l, r);
                    std::swap(vec[i], vec.back());
                    vec.pop_back();
                }
            }
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 4 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 66 ms 15636 KB Output is correct
3 Correct 62 ms 15616 KB Output is correct
4 Correct 59 ms 15612 KB Output is correct
5 Correct 53 ms 15636 KB Output is correct
6 Correct 75 ms 15652 KB Output is correct
7 Correct 34 ms 15064 KB Output is correct
8 Correct 57 ms 15700 KB Output is correct
9 Correct 39 ms 15108 KB Output is correct
10 Correct 48 ms 15144 KB Output is correct
11 Correct 45 ms 15140 KB Output is correct
12 Correct 44 ms 15412 KB Output is correct
13 Correct 36 ms 15404 KB Output is correct
14 Correct 57 ms 16308 KB Output is correct
15 Correct 57 ms 15792 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 4 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 66 ms 15636 KB Output is correct
3 Correct 62 ms 15616 KB Output is correct
4 Correct 59 ms 15612 KB Output is correct
5 Correct 53 ms 15636 KB Output is correct
6 Correct 75 ms 15652 KB Output is correct
7 Correct 34 ms 15064 KB Output is correct
8 Correct 57 ms 15700 KB Output is correct
9 Correct 39 ms 15108 KB Output is correct
10 Correct 48 ms 15144 KB Output is correct
11 Correct 45 ms 15140 KB Output is correct
12 Correct 44 ms 15412 KB Output is correct
13 Correct 36 ms 15404 KB Output is correct
14 Correct 57 ms 16308 KB Output is correct
15 Correct 57 ms 15792 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 529 ms 15652 KB Output is correct
18 Correct 399 ms 15692 KB Output is correct
19 Correct 543 ms 15692 KB Output is correct
20 Correct 540 ms 15732 KB Output is correct
21 Correct 505 ms 15768 KB Output is correct
22 Correct 377 ms 15660 KB Output is correct
23 Correct 498 ms 15636 KB Output is correct
24 Correct 563 ms 15844 KB Output is correct
25 Correct 515 ms 15736 KB Output is correct
26 Correct 601 ms 15736 KB Output is correct
27 Correct 345 ms 15672 KB Output is correct
28 Correct 389 ms 15684 KB Output is correct
29 Correct 449 ms 15596 KB Output is correct
30 Correct 648 ms 15272 KB Output is correct
31 Correct 667 ms 15172 KB Output is correct
32 Correct 805 ms 15276 KB Output is correct
33 Correct 442 ms 15188 KB Output is correct
34 Correct 695 ms 15056 KB Output is correct
35 Correct 493 ms 15028 KB Output is correct
36 Correct 419 ms 15344 KB Output is correct
37 Correct 388 ms 15304 KB Output is correct
38 Correct 321 ms 15564 KB Output is correct
39 Correct 393 ms 16324 KB Output is correct
40 Correct 328 ms 15916 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 66 ms 15636 KB Output is correct
3 Correct 62 ms 15616 KB Output is correct
4 Correct 59 ms 15612 KB Output is correct
5 Correct 53 ms 15636 KB Output is correct
6 Correct 75 ms 15652 KB Output is correct
7 Correct 34 ms 15064 KB Output is correct
8 Correct 57 ms 15700 KB Output is correct
9 Correct 39 ms 15108 KB Output is correct
10 Correct 48 ms 15144 KB Output is correct
11 Correct 45 ms 15140 KB Output is correct
12 Correct 44 ms 15412 KB Output is correct
13 Correct 36 ms 15404 KB Output is correct
14 Correct 57 ms 16308 KB Output is correct
15 Correct 57 ms 15792 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 4064 ms 15608 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 4 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -