Submission #336625

#	Time	Username	Problem	Language	Result	Execution time	Memory
336625		KoD	3단 점프 (JOI19_jumps)	C++17	100 / 100	1020 ms	92404 KiB

jumps

#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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54