oj.uz

Submission #336625

# Submission time Handle Problem Language Result Execution time Memory
336625 2020-12-16T03:39:50 Z KoD Triple Jump (JOI19_jumps) C++17
100 / 100
 1020 ms 92404 KB 
#include <bits/stdc++.h>

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

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

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

struct Mn {
    u32 whole, value;
    static Mn id() {
        return Mn { 0, 0 };
    }
    Mn operator + (const Mn other) const {
        return Mn { std::max(whole, other.whole), std::max(value, other.value) };
    }
};

struct Ef {
    u32 add;
    static Ef id() {
        return Ef { 0 };
    }
    Ef operator + (const Ef other) const {
        return Ef { std::max(add, other.add) };
    }
};

Mn operator + (const Mn mn, const Ef ef) {
    return Mn { std::max(mn.whole, mn.value + ef.add), mn.value };
}

struct Segtree {
    struct Node {
        Mn mn;
        Ef ef;
    };

    void fetch(const usize i) {
        data[i].mn = data[i * 2 + 0].mn + data[i * 2 + 1].mn;
    }
    void apply(const usize i, const Ef ef) {
        data[i].mn = data[i].mn + ef;
        data[i].ef = data[i].ef + ef;
    }
    void flush(const usize i) {
        apply(i * 2 + 0, data[i].ef);
        apply(i * 2 + 1, data[i].ef);
    }

    static usize ctzr(const usize i) {
        return __builtin_ctzll(i);
    }
    static usize height(const usize i) {
        return 64 - __builtin_clzll(i);
    }

    void pushdown(const usize i) {
        const auto lsb = ctzr(i);
        for (usize d = height(i); --d > lsb;) {
            flush(i >> d);
        }
    }
    void pullup(usize i) {
        i >>= ctzr(i);
        while (i != 1) {
            i >>= 1;
            fetch(i);
        }
    }

    std::vector<Node> data;
    Segtree(const std::vector<u32> &vec) {
        const auto size = vec.size();
        data.resize(size * 2, Node { Mn::id(), Ef::id() });
        for (usize i = 0; i < size; ++i) {
            data[size + i].mn.whole = vec[i];
            data[size + i].mn.value = vec[i];
        }
        for (usize i = size - 1; i > 0; --i) {
            fetch(i);
        }
    }

    void operate(usize l, usize r, const u32 x) {
        l += size();
        r += size();
        pushdown(l);
        pushdown(r);
        const auto cl = l;
        const auto cr = r;
        const auto ef = Ef { x };
        while (l < r) {
            if (l & 1) {
                apply(l, ef);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                apply(r, ef);
            }
            l >>= 1;
            r >>= 1;
        }
        pullup(cl);
        pullup(cr);
    }

    u32 fold(usize l, usize r) {
        l += size();
        r += size();
        pushdown(l);
        pushdown(r);
        Mn mn = Mn::id();
        while (l < r) {
            if (l & 1) {
                mn = mn + data[l].mn;
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                mn = mn + data[r].mn;
            }
            l >>= 1;
            r >>= 1;
        }
        return mn.whole;
    } 

    usize size() const {
        return data.size() / 2;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    usize N;
    std::cin >> N;
    Vec<u32> A(N);
    for (auto &x: A) {
        std::cin >> x;
    }
    std::vector<std::vector<usize>> cand(N);
    std::stack<usize> stack;
    for (usize m = 0; m < N - 1; ++m) {
        while (!stack.empty()) {
            const auto l = stack.top();
            if (m + (m - l) < N) {
                cand[l].push_back(m);
            }
            if (A[l] > A[m]) {
                break;
            }
            stack.pop();
        }
        stack.push(m);
    }
    usize Q;
    std::cin >> Q;
    std::vector<std::vector<std::pair<usize, usize>>> query(N);
    for (usize i = 0; i < Q; ++i) {
        usize l, r;
        std::cin >> l >> r;
        l -= 1;
        query[l].emplace_back(i, r);
    }
    Segtree seg(A);
    std::vector<usize> ans(Q);
    for (usize l = N; l --> 0;) {
        for (const auto m: cand[l]) {
            const auto r = m + (m - l);
            seg.operate(r, N, A[l] + A[m]);
        }
        for (const auto [i, r]: query[l]) {
            ans[i] = seg.fold(l + 2, r);
        }
    }
    for (const auto x: ans) {
        std::cout << x << '\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 322 ms 27968 KB Output is correct
12 Correct 316 ms 27928 KB Output is correct
13 Correct 292 ms 27884 KB Output is correct
14 Correct 311 ms 28012 KB Output is correct
15 Correct 308 ms 27964 KB Output is correct
16 Correct 314 ms 27372 KB Output is correct
17 Correct 298 ms 27360 KB Output is correct
18 Correct 305 ms 27216 KB Output is correct
19 Correct 293 ms 27884 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 24428 KB Output is correct
2 Correct 98 ms 23148 KB Output is correct
3 Correct 101 ms 24812 KB Output is correct
4 Correct 167 ms 24556 KB Output is correct
5 Correct 187 ms 24428 KB Output is correct
6 Correct 165 ms 23916 KB Output is correct
7 Correct 164 ms 23788 KB Output is correct
8 Correct 168 ms 23916 KB Output is correct
9 Correct 167 ms 24164 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 322 ms 27968 KB Output is correct
12 Correct 316 ms 27928 KB Output is correct
13 Correct 292 ms 27884 KB Output is correct
14 Correct 311 ms 28012 KB Output is correct
15 Correct 308 ms 27964 KB Output is correct
16 Correct 314 ms 27372 KB Output is correct
17 Correct 298 ms 27360 KB Output is correct
18 Correct 305 ms 27216 KB Output is correct
19 Correct 293 ms 27884 KB Output is correct
20 Correct 168 ms 24428 KB Output is correct
21 Correct 98 ms 23148 KB Output is correct
22 Correct 101 ms 24812 KB Output is correct
23 Correct 167 ms 24556 KB Output is correct
24 Correct 187 ms 24428 KB Output is correct
25 Correct 165 ms 23916 KB Output is correct
26 Correct 164 ms 23788 KB Output is correct
27 Correct 168 ms 23916 KB Output is correct
28 Correct 167 ms 24164 KB Output is correct
29 Correct 1020 ms 88912 KB Output is correct
30 Correct 812 ms 86308 KB Output is correct
31 Correct 812 ms 90296 KB Output is correct
32 Correct 998 ms 89324 KB Output is correct
33 Correct 994 ms 89280 KB Output is correct
34 Correct 991 ms 87164 KB Output is correct
35 Correct 1012 ms 86652 KB Output is correct
36 Correct 1000 ms 86632 KB Output is correct
37 Correct 1006 ms 88300 KB Output is correct
38 Correct 740 ms 91884 KB Output is correct
39 Correct 731 ms 92012 KB Output is correct
40 Correct 718 ms 88588 KB Output is correct
41 Correct 719 ms 88112 KB Output is correct
42 Correct 727 ms 88208 KB Output is correct
43 Correct 725 ms 89804 KB Output is correct
44 Correct 762 ms 92176 KB Output is correct
45 Correct 755 ms 92268 KB Output is correct
46 Correct 753 ms 89108 KB Output is correct
47 Correct 740 ms 88812 KB Output is correct
48 Correct 743 ms 88556 KB Output is correct
49 Correct 748 ms 90732 KB Output is correct
50 Correct 835 ms 92364 KB Output is correct
51 Correct 824 ms 92404 KB Output is correct
52 Correct 812 ms 89964 KB Output is correct
53 Correct 810 ms 89708 KB Output is correct
54 Correct 815 ms 89704 KB Output is correct
55 Correct 813 ms 91208 KB Output is correct