Submission #330948

#	Time	Username	Problem	Language	Result	Execution time	Memory
330948		jungsnow	Triple Jump (JOI19_jumps)	C++14	100 / 100	1367 ms	136080 KiB

jumps

///refers to Maripium's code
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn = 500100;
const ll inf = 1e18;

struct sta {
    ll pref, ans, suf;
    sta() : pref(-inf), ans(-inf), suf(-inf) {}
    friend sta operator + (const sta &l, const sta &r) {
        sta ans;
        ans.pref = max(l.pref, r.pref);
        ans.suf = max(l.suf, r.suf);
        ans.ans = max({l.ans, r.ans, l.pref + r.suf});
        return ans;
    }
};

ll A[maxn], Ans[maxn];
sta T[maxn << 2];
vector<pair<int, ll>> es[maxn];
vector<pair<int, int>> qs[maxn];

void build(int v, int l, int r) {
    if (l == r) {
        T[v].suf = A[l];
        return;
    }
    int md = (l + r) >> 1;
    build(v << 1, l, md);
    build(v << 1 | 1, md + 1, r);
    T[v] = T[v << 1] + T[v << 1 | 1];
}

void upd(int v, int l, int r, int pos, ll val) {
    if (l == r) {
        T[v].pref = max(T[v].pref, val);
        return;
    }
    int md = (l + r) >> 1;
    if (pos <= md)
        upd(v << 1, l, md, pos, val);
    else
        upd(v << 1 | 1, md + 1, r, pos, val);
    T[v] = T[v << 1] + T[v << 1 | 1];
}

sta get(int v, int l, int r, int L, int R) {
    if (L > r || R < l) return sta();
    if (L <= l && r <= R) {
        return T[v];
    }
    int md = (l + r) >> 1;
    return get(v << 1, l, md, L, R) + get(v << 1 | 1, md + 1, r, L, R);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    stack<int> st;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        while (!st.empty()) {
            int id = 2 * i - st.top() - 1;
            if (id < N) es[st.top()].emplace_back(A[i] + A[st.top()], id);
            if (A[i] < A[st.top()]) break;
            else st.pop();
        }
        st.push(i);
    }
    int Q; cin >> Q;
    for (int l, r, i = 1; i <= Q; ++i) {
        cin >> l >> r;
        qs[l].emplace_back(r, i);
    }
    build(1, 1, N);
    for (int i = N; i >= 1; --i) {
        for (auto e : es[i]) {
            upd(1, 1, N, e.second, e.first);
        }
        for (auto q : qs[i]) {
            Ans[q.second] = get(1, 1, N, i, q.first).ans;
        }
    }
    for (int i = 1; i <= Q; ++i) {
        cout << Ans[i] << '\n';
    }
    return 0;
}

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