Submission #853674

#	Time	Username	Problem	Language	Result	Execution time	Memory
853674		Tam_theguide	Triple Jump (JOI19_jumps)	C++14	100 / 100	782 ms	112012 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;
const int N = 5e5 + 5;
int n, q, a[N], l[N], r[N];
stack<int> st;
using pii = pair<int, int>;
#define fi first
#define se second

vector<pii> query_l[N];
vector<int> being_i[N];

ll tot[4*N], seg[4*N], lazy[4*N], res[N];

void build(int root, int tl, int tr) {
    lazy[root] = -INF;
    if (tl == tr) {
        seg[root] = a[tl];
        tot[root] = seg[root] + lazy[root];
        return;
    }

    int tm = (tl + tr) / 2;
    build(2*root, tl, tm);
    build(2*root+1, tm+1, tr);
    seg[root] = max(seg[2*root], seg[2*root+1]);
    tot[root] = max(tot[2*root], tot[2*root+1]);
}

void cmax(ll &x, ll y) {x = max(x, y);}
void upd(int root, ll v) {
    cmax(lazy[root], v);
    cmax(tot[root], seg[root] + lazy[root]);
}

void update(int root, int tl, int tr, int l, int r, ll v) {
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
        upd(root, v);
        return;
    }

    int tm = (tl + tr) / 2;
    upd(2*root, lazy[root]);
    upd(2*root+1, lazy[root]);
    update(2*root, tl, tm, l, r, v);
    update(2*root+1, tm+1, tr, l, r, v);
    tot[root] = max(tot[2*root], tot[2*root+1]);
}

ll get(int root, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return 0LL;
    if (tl >= l && tr <= r) return tot[root];

    int tm = (tl + tr) / 2;
    upd(2*root, lazy[root]);
    upd(2*root+1, lazy[root]);
    return max(get(2*root, tl, tm, l, r),
               get(2*root+1, tm+1, tr, l, r));
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("triple.inp", "r", stdin);
    //freopen("triple.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        l[i] = 0, r[i] = n+1;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) l[i] = st.top();
        st.push(i);
    }

    while (!st.empty()) st.pop();

    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) r[i] = st.top();
        st.push(i);
    }

    for (int i = 1; i <= n; i++) {
        if (l[i] > 0) being_i[l[i]].push_back(i);
        if (r[i] < n+1) being_i[i].push_back(r[i]);
    }

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        query_l[x].emplace_back(y, i);
    }

    build(1, 1, n);
    for (int i = n; i >= 1; i--) {
        for (auto c: being_i[i]) {
            update(1, 1, n, 2*c - i, n, a[c] + a[i]);
        }
        for (auto c: query_l[i]) {
            res[c.se] = get(1, 1, n, i, c.fi);
        }
    }

    for (int i = 1; i <= q; i++) cout << res[i] << '\n';
}

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