Submission #1288879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288879		MinhKien	Triple Jump (JOI19_jumps)	C++20	100 / 100	782 ms	95144 KiB

jumps

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

#define ll long long

const int N = 5e5 + 10;

int n, m, a[N];
ll ans[N];
vector <int> v[N], Q[N];
stack <int> st;

struct query {
    int l, r;
} q[N];

struct SEG {
    struct node {
        ll one, two, val;

        node operator + (const node &o) const {
            node res;
            res.one = max(one, o.one);
            res.two = max(two, o.two);
            res.val = max(max(val, o.val), two + o.one);
            return res;
        }
    } st[N << 2];

    void build(int l, int r, int id) {
        if (l == r) {
            st[id].one = a[l];
            st[id].two = st[id].val = 0;
            return;
        }

        int mid = (l + r) >> 1;
        build(l, mid, id << 1);
        build(mid + 1, r, id << 1 | 1);

        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    void update(int l, int r, int u, ll VAL, int id) {
        if (l == r) {
            st[id].two = max(st[id].two, VAL);
            st[id].val = st[id].one + st[id].two;
            return;
        }

        int mid = (l + r) >> 1;
        if (u <= mid) update(l, mid, u, VAL, id << 1);
        else update(mid + 1, r, u, VAL, id << 1 | 1);

        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    node get(int l, int r, int u, int v, int id) {
        if (l > v || r < u) return st[0];

        if (l >= u && r <= v) return st[id];

        int mid = (l + r) >> 1;
        return get(l, mid, u, v, id << 1) + get(mid + 1, r, u, v, id << 1 | 1);
    }
} seg;

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];

        while (!st.empty() && a[st.top()] <= a[i]) {
            v[st.top()].push_back(i);
            st.pop();
        }

        if (!st.empty()) v[st.top()].push_back(i);
        st.push(i);
    }

    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> q[i].l >> q[i].r;
        Q[q[i].l].push_back(i);
    }

    seg.build(1, n, 1);
    for (int i = n; i >= 1; --i) {
        for (int z: v[i]) {
            int nxt = 2 * z - i;
            if (nxt <= n) {
                seg.update(1, n, nxt, a[i] + a[z], 1);
            }
        }

        for (int z: Q[i]) {
            SEG::node cur = seg.get(1, n, q[z].l, q[z].r, 1);
            ans[z] = cur.val;
        }
    }

    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}

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