Submission #1291129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291129		baotoan655	Triple Jump (JOI19_jumps)	C++20	100 / 100	598 ms	90420 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int nmax = 500005;
vector< pair<int, int> > l[nmax], qr[nmax];
int v[nmax], st[nmax], an[nmax];
int n, i, j, u, q, L, R;
struct node {
    int L, R, LR;
} arb[4 * nmax], ans;
void add(int x, int y) {
    if(2 * y - x <= n)
        l[x].push_back({2 * y - x, v[x] + v[y]});
}
void mrg(node &A, node B, node C) {
    A.L = max(B.L, C.L);
    A.R = max(B.R, C.R);
    A.LR = max(B.LR, C.LR);
    A.LR = max(A.LR, B.L + C.R);
}
void update(int nod, int l, int r, int poz, int val, int tip) {
    if(l == r) {
        if(tip) arb[nod].R = max(arb[nod].R, val);
        else arb[nod].L = max(arb[nod].L, val);
        arb[nod].LR = arb[nod].L + arb[nod].R;
        return;
    }
    int m = (l + r) / 2;
    if(poz <= m) update(2 * nod, l, m, poz, val, tip);
    else update(2 * nod + 1, m + 1, r, poz, val, tip);
    mrg(arb[nod], arb[2 * nod], arb[2 * nod + 1]);
}
void query(int nod, int l, int r, int st, int dr) {
    if(st <= l && r <= dr) {
        mrg(ans, ans, arb[nod]);
        return;
    }
    int m = (l + r) / 2;
    if(st <= m) query(2 * nod, l, m, st, dr);
    if(m < dr)  query(2 * nod + 1, m + 1, r, st, dr);
}
int Q(int S, int D) {
    ans = {-(1 << 29), -(1 << 29), -(1 << 29)};
    query(1, 1, n, S, D);
    return ans.LR;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> v[i];
        while(u > 0 && v[i] > v[st[u]]) {
            add(st[u], i);
            u--;
        }
        if(u) add(st[u], i);
        st[++u] = i;
    }
    cin >> q;
    for(i = 1; i <= q; i++) {
        cin >> L >> R;
        qr[L].push_back({R, i});
    }
    for(i = 1; i <= 4 * n; i++) {
        arb[i].L = arb[i].R = arb[i].LR = -(1 << 29);
    }
    for(i = n; i >= 1; i--) {
        update(1, 1, n, i, v[i], 1);
        for(auto it : l[i])
            update(1, 1, n, it.first, it.second, 0);
        for(auto it : qr[i])
            an[it.second] = Q(i, it.first);
    }
    for(i = 1; i <= q; i++)
        cout << an[i] << '\n';
    return 0;
}

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