oj.uz

Submission #402261

# Submission time Handle Problem Language Result Execution time Memory
402261 2021-05-11T13:11:00 Z KoD Triple Jump (JOI19_jumps) C++17
100 / 100
 1308 ms 89000 KB 
#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

class revrep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { --itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr revrep(const usize first, const usize last) noexcept
        : first(last - 1), last(std::min(first, last) - 1) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr u64 ceil_log2(const u64 x) {
    u64 e = 0;
    while (((u64)1 << e) < x) ++e;
    return e;
}

constexpr u64 bit_rzeros(const u64 x) { return x == 0 ? 64 : __builtin_ctzll(x); }

template <class Monoid, class Effector> class LazySegmentTree {
    using M = Monoid;
    using E = Effector;
    usize internal_size, logn, seg_size;
    std::vector<M> data;
    std::vector<E> lazy;

    void fetch(const usize k) { data[k] = data[2 * k] + data[2 * k + 1]; }
    void apply(const usize k, const E& e) {
        data[k] = data[k] * e;
        if (k < seg_size) lazy[k] = lazy[k] * e;
    }
    void flush(const usize k) {
        apply(2 * k, lazy[k]);
        apply(2 * k + 1, lazy[k]);
        lazy[k] = E::one();
    }

    void push(const usize k) {
        for (const usize d : revrep(bit_rzeros(k) + 1, logn + 1)) flush(k >> d);
    }
    void pull(usize k) {
        for (k >>= bit_rzeros(k); k > 1;) fetch(k >>= 1);
    }

  public:
    explicit LazySegmentTree(const usize size = 0, const M& value = M::zero())
        : LazySegmentTree(std::vector<M>(size, value)) {}
    explicit LazySegmentTree(const std::vector<M>& vec) : internal_size(vec.size()) {
        logn = ceil_log2(internal_size);
        seg_size = 1 << logn;
        data = std::vector<M>(2 * seg_size, M::zero());
        lazy = std::vector<E>(seg_size, E::one());
        for (const usize i : rep(0, internal_size)) data[seg_size + i] = vec[i];
        for (const usize i : revrep(1, seg_size)) fetch(i);
    }

    usize size() const { return internal_size; }

    void assign(usize i, const M& value) {
        assert(i < internal_size);
        i += seg_size;
        for (const usize d : revrep(1, logn + 1)) flush(i >> d);
        data[i] = value;
        for (const usize d : rep(1, logn + 1)) fetch(i >> d);
    }
    void operate(usize l, usize r, const E& e) {
        assert(l <= r and r <= internal_size);
        l += seg_size;
        r += seg_size;
        push(l);
        push(r);
        for (usize l0 = l, r0 = r; l0 < r0; l0 >>= 1, r0 >>= 1) {
            if (l0 & 1) apply(l0++, e);
            if (r0 & 1) apply(--r0, e);
        }
        pull(l);
        pull(r);
    }

    M fold() const { return data[1]; }
    M fold(usize l, usize r) {
        assert(l <= r and r <= internal_size);
        l += seg_size;
        r += seg_size;
        push(l);
        push(r);
        M ret_l = M::zero(), ret_r = M::zero();
        while (l < r) {
            if (l & 1) ret_l = ret_l + data[l++];
            if (r & 1) ret_r = data[--r] + ret_r;
            l >>= 1;
            r >>= 1;
        }
        return ret_l + ret_r;
    }

    template <class F> usize max_right(usize l, const F& f) {
        assert(l <= internal_size);
        assert(f(M::zero()));
        if (l == internal_size) return internal_size;
        l += seg_size;
        for (const usize d : revrep(1, logn + 1)) flush(l >> d);
        M sum = M::zero();
        do {
            while (!(l & 1)) l >>= 1;
            if (!f(sum + data[l])) {
                while (l < seg_size) {
                    flush(l);
                    l = 2 * l;
                    if (f(sum + data[l])) sum = sum + data[l++];
                }
                return l - seg_size;
            }
            sum = sum + data[l++];
        } while ((l & -l) != l);
        return internal_size;
    }

    template <class F> usize min_left(usize r, const F& f) {
        assert(r <= internal_size);
        assert(f(M::zero()));
        if (r == 0) return 0;
        r += seg_size;
        for (const usize d : revrep(1, logn + 1)) flush((r - 1) >> d);
        M sum = M::zero();
        do {
            r -= 1;
            while (r > 1 and (r & 1)) r >>= 1;
            if (!f(data[r] + sum)) {
                while (r < seg_size) {
                    flush(r);
                    r = 2 * r + 1;
                    if (f(data[r] + sum)) sum = data[r--] + sum;
                }
                return r + 1 - seg_size;
            }
            sum = data[r] + sum;
        } while ((r & -r) != r);
        return 0;
    }
};

template <class T> using Vec = std::vector<T>;

struct Monoid {
    u32 max, base;
    static Monoid zero() { return Monoid{0, 0}; }
    Monoid operator+(const Monoid& other) const { return Monoid{std::max(max, other.max), std::max(base, other.base)}; }
};

struct Effector {
    u32 add;
    static Effector one() { return Effector{0}; }
    Effector operator*(const Effector& other) const { return Effector{std::max(add, other.add)}; }
};

Monoid operator*(const Monoid& m, const Effector& e) { return Monoid{std::max(m.max, m.base + e.add), m.base}; }

void JOI19_jumps_main() {
    usize N;
    std::cin >> N;
    Vec<u32> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    Vec<Vec<usize>> cand(N);
    std::stack<usize> stack;
    for (const auto i : rep(0, N)) {
        while (!stack.empty() and A[stack.top()] <= A[i]) {
            const auto j = stack.top();
            stack.pop();
            cand[j].push_back(i);
        }
        if (!stack.empty()) {
            const auto j = stack.top();
            cand[j].push_back(i);
        }
        stack.push(i);
    }
    usize Q;
    std::cin >> Q;
    Vec<Vec<std::pair<usize, usize>>> query(N);
    for (const auto i : rep(0, Q)) {
        usize l, r;
        std::cin >> l >> r;
        l -= 1;
        query[l].emplace_back(i, r);
    }
    LazySegmentTree<Monoid, Effector> seg(N);
    for (const auto i : rep(0, N)) {
        seg.assign(i, Monoid{0, A[i]});
    }
    Vec<u32> ans(Q);
    for (const auto l : revrep(0, N)) {
        for (const auto m : cand[l]) {
            const auto r = 2 * m - l;
            if (r < N) {
                seg.operate(r, N, Effector{A[l] + A[m]});
            }
        }
        for (const auto [i, r] : query[l]) {
            ans[i] = seg.fold(l + 2, r).max;
        }
    }
    for (const auto x : ans) {
        std::cout << x << '\n';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    JOI19_jumps_main();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 271 ms 26016 KB Output is correct
12 Correct 267 ms 25924 KB Output is correct
13 Correct 278 ms 25972 KB Output is correct
14 Correct 264 ms 25996 KB Output is correct
15 Correct 261 ms 26056 KB Output is correct
16 Correct 265 ms 25400 KB Output is correct
17 Correct 283 ms 25356 KB Output is correct
18 Correct 267 ms 25156 KB Output is correct
19 Correct 319 ms 25980 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 24644 KB Output is correct
2 Correct 137 ms 25088 KB Output is correct
3 Correct 142 ms 26748 KB Output is correct
4 Correct 208 ms 26340 KB Output is correct
5 Correct 211 ms 26304 KB Output is correct
6 Correct 208 ms 25748 KB Output is correct
7 Correct 226 ms 25532 KB Output is correct
8 Correct 206 ms 25536 KB Output is correct
9 Correct 217 ms 25904 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 271 ms 26016 KB Output is correct
12 Correct 267 ms 25924 KB Output is correct
13 Correct 278 ms 25972 KB Output is correct
14 Correct 264 ms 25996 KB Output is correct
15 Correct 261 ms 26056 KB Output is correct
16 Correct 265 ms 25400 KB Output is correct
17 Correct 283 ms 25356 KB Output is correct
18 Correct 267 ms 25156 KB Output is correct
19 Correct 319 ms 25980 KB Output is correct
20 Correct 211 ms 24644 KB Output is correct
21 Correct 137 ms 25088 KB Output is correct
22 Correct 142 ms 26748 KB Output is correct
23 Correct 208 ms 26340 KB Output is correct
24 Correct 211 ms 26304 KB Output is correct
25 Correct 208 ms 25748 KB Output is correct
26 Correct 226 ms 25532 KB Output is correct
27 Correct 206 ms 25536 KB Output is correct
28 Correct 217 ms 25904 KB Output is correct
29 Correct 1103 ms 85732 KB Output is correct
30 Correct 891 ms 82584 KB Output is correct
31 Correct 992 ms 86768 KB Output is correct
32 Correct 1126 ms 85760 KB Output is correct
33 Correct 1177 ms 85776 KB Output is correct
34 Correct 1124 ms 83520 KB Output is correct
35 Correct 1137 ms 83196 KB Output is correct
36 Correct 1308 ms 83116 KB Output is correct
37 Correct 1140 ms 84540 KB Output is correct
38 Correct 905 ms 88364 KB Output is correct
39 Correct 872 ms 88332 KB Output is correct
40 Correct 888 ms 85124 KB Output is correct
41 Correct 837 ms 84556 KB Output is correct
42 Correct 895 ms 84476 KB Output is correct
43 Correct 934 ms 86200 KB Output is correct
44 Correct 896 ms 88740 KB Output is correct
45 Correct 907 ms 88612 KB Output is correct
46 Correct 871 ms 85456 KB Output is correct
47 Correct 953 ms 85096 KB Output is correct
48 Correct 874 ms 85104 KB Output is correct
49 Correct 915 ms 87172 KB Output is correct
50 Correct 957 ms 89000 KB Output is correct
51 Correct 956 ms 88900 KB Output is correct
52 Correct 935 ms 86456 KB Output is correct
53 Correct 943 ms 86052 KB Output is correct
54 Correct 947 ms 86104 KB Output is correct
55 Correct 1010 ms 87780 KB Output is correct