Submission #1152523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152523		Hamed_Ghaffari	Triple Jump (JOI19_jumps)	C++20	100 / 100	1095 ms	78636 KiB

jumps

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

using pii = pair<int, int>;

#define mid ((l+r)>>1)
#define lc (id<<1)
#define rc (lc|1)
#define maxs(a,b) (a=max(a,b))
#define pb push_back

const int MXN = 5e5+5;

int n, q, a[MXN], L[MXN], R[MXN], ans[MXN];
vector<pii> Q[MXN];
vector<int> g[MXN];

int seg[MXN<<2], hseg[MXN<<2], lz[MXN<<2], hlz[MXN<<2];
inline void apply(int x, int id) {
    maxs(hseg[id], seg[id]+=x);
    maxs(hlz[id], lz[id]+=x);
}
inline void push(int id) {
    maxs(hseg[lc], seg[lc]+hlz[id]);
    seg[lc] += lz[id];
    maxs(hlz[lc], lz[lc]+hlz[id]);
    lz[lc] += lz[id];
    maxs(hseg[rc], seg[rc]+hlz[id]);
    seg[rc] += lz[id];
    maxs(hlz[rc], lz[rc]+hlz[id]);
    lz[rc] += lz[id];

    hlz[id] = lz[id] = 0;
}
void upd(int s, int e, int x, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) {
        apply(x, id);
        return;
    }
    push(id);
    if(s<mid) upd(s, e, x, l, mid, lc);
    if(e>mid) upd(s, e, x, mid, r, rc);
    seg[id] = max(seg[lc], seg[rc]);
    hseg[id] = max(hseg[lc], hseg[rc]);
}
int get(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) return hseg[id];
    push(id);
    if(e<=mid) return get(s, e, l, mid, lc);
    if(s>=mid) return get(s, e, mid, r, rc);
    return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}


int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        for(L[i]=i-1; L[i]&&a[L[i]]<a[i]; L[i]=L[L[i]]);
        if(L[i]) g[L[i]].pb(i);
    }
    for(int i=n; i>=1; i--)
        for(R[i]=i+1; R[i]<=n&&a[R[i]]<a[i]; R[i]=R[R[i]]);
    cin >> q;
    for(int i=1,l,r; i<=q; i++) {
        cin >> l >> r;
        Q[l].pb(pii(r, i));
    }
    for(int i=1; i<=n; i++) upd(i, i+1, a[i]);
    for(int i=n; i>=1; i--) {
        for(int j : g[i])
            if(2*j-i<=n)
                upd(2*j-i, n+1, a[i]+a[j]),
                upd(2*j-i, n+1, -a[i]-a[j]);
        if(2*R[i]-i<=n)
            upd(2*R[i]-i, n+1, a[i]+a[R[i]]),
            upd(2*R[i]-i, n+1, -a[i]-a[R[i]]);
        for(auto [r, id] : Q[i])
            ans[id] = get(i, r+1);
    }
    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