Submission #1253448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253448		ankite	Triple Jump (JOI19_jumps)	C++20	27 / 100	89 ms	83104 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = -(ll)1e18;

struct SegmentTree {
    int n, size;
    vector<ll> data;

    SegmentTree(int _n) {
        n = _n;
        size = 1;
        while (size < n) size <<= 1;
        data.assign(2 * size, NEG_INF);
    }

    void update(int i, ll val) {
        i += size;
        data[i] = max(data[i], val);
        for (i >>= 1; i > 0; i >>= 1)
            data[i] = max(data[2*i], data[2*i + 1]);
    }

    ll query(int l, int r) {
        ll res = NEG_INF;
        l += size; r += size;
        while (l <= r) {
            if (l & 1) res = max(res, data[l++]);
            if (!(r & 1)) res = max(res, data[r--]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<ll> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    int q;
    cin >> q;
    vector<tuple<int,int,int>> queries(q);
    for (int i = 0; i < q; i++) {
        int L, R;
        cin >> L >> R;
        --L; --R;
        queries[i] = {L, R, i};
    }

    int LOG = __lg(n) + 1;
    vector<vector<pair<ll,int>>> st_table(LOG, vector<pair<ll,int>>(n));
    for (int i = 0; i < n; i++) {
        st_table[0][i] = {A[i], i};
    }
    for (int j = 1; j < LOG; j++) {
        int step = 1 << (j - 1);
        for (int i = 0; i + (1 << j) <= n; i++) {
            auto [lv, li] = st_table[j-1][i];
            auto [rv, ri] = st_table[j-1][i + step];
            if (lv > rv)
                st_table[j][i] = {lv, li};
            else if (rv > lv)
                st_table[j][i] = {rv, ri};
            else
                st_table[j][i] = {lv, min(li, ri)};
        }
    }
    auto query_range_max = [&](int l, int r) {
        if (l > r) return make_pair(NEG_INF, -1);
        int len = r - l + 1;
        int j = __lg(len);
        auto seg1 = st_table[j][l];
        auto seg2 = st_table[j][r - (1 << j) + 1];
        if (seg1.first > seg2.first) return seg1;
        if (seg2.first > seg1.first) return seg2;
        return make_pair(seg1.first, min(seg1.second, seg2.second));
    };

    vector<vector<int>> nxt(n);
    vector<int> stck;
    for (int i = 0; i < n; i++) {
        while (!stck.empty() && A[stck.back()] < A[i]) {
            nxt[stck.back()].push_back(i);
            stck.pop_back();
        }
        if (!stck.empty()) {
            nxt[stck.back()].push_back(i);
        }
        stck.push_back(i);
    }

    vector<tuple<int,int,ll>> events;
    events.reserve(n);
    for (int i = 0; i < n; i++) {
        for (int j : nxt[i]) {
            int k_low = 2*j - i;
            if (k_low < n) {
                auto [val, idx] = query_range_max(k_low, n-1);
                ll total = A[i] + A[j] + val;
                events.emplace_back(idx, i, total);
            }
        }
    }
    sort(events.begin(), events.end(), [](auto &a, auto &b){ return get<0>(a) < get<0>(b); });

    auto queries_sorted = queries;
    sort(queries_sorted.begin(), queries_sorted.end(), [](auto &a, auto &b){
        return get<1>(a) < get<1>(b);
    });

    SegmentTree seg(n);
    vector<ll> ans(q, NEG_INF);
    int e_ptr = 0, qry_ptr = 0;

    for (int R = 0; R < n; R++) {
        while (e_ptr < (int)events.size() && get<0>(events[e_ptr]) <= R) {
            int i = get<1>(events[e_ptr]);
            ll v = get<2>(events[e_ptr]);
            seg.update(i, v);
            e_ptr++;
        }
        while (qry_ptr < q && get<1>(queries_sorted[qry_ptr]) == R) {
            int l0, r0, idx;
            tie(l0, r0, idx) = queries_sorted[qry_ptr];
            ans[idx] = seg.query(l0, n-1);
            qry_ptr++;
        }
    }

    for (ll x : ans) {
        cout << x << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54