Submission #464282

#	Time	Username	Problem	Language	Result	Execution time	Memory
464282		NintsiChkhaidze	Triple Jump (JOI19_jumps)	C++14	100 / 100	1218 ms	87872 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pi pair<int,int>
#define s second
#define f first
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 500005;
int ans[N],t[4*N],add[4*N],T[4*N],n,a[N];
vector <pi> v[N];
vector <int> nx[N];
stack <int> st;

void go(){
    for (int i = 1; i <= n; i++){
        while (st.size() && a[i] >= a[st.top()]){
            nx[st.top()].pb(i);
            st.pop();
        }
        
        if (st.size())
            nx[st.top()].pb(i);
        
        st.push(i);
    }
}

void build(int h,int l,int r){
    if (l == r){
        T[h] = a[l];
        return;
    }
    build(left),build(right);
    T[h] = max(T[h*2],T[h*2+1]);
}

void push(int h){
    if (!add[h]) return;
    t[h*2] = max(t[h*2],T[h*2] + add[h]);
    t[h*2 + 1] = max(t[h*2 + 1],T[h*2 + 1] + add[h]);
    
    add[h*2] = max(add[h*2],add[h]);
    add[h*2 + 1] = max(add[h*2 + 1],add[h]);
    
    add[h] = 0;
}
void upd(int h,int l,int r,int L,int R,int val){
    if (r < L || R < l) return;
    if (L <= l && r <= R){
        t[h] = max(T[h] + val,t[h]);
        add[h] = max(add[h],val);
        return;
    }
    
    push(h);
    upd(left,L,R,val),upd(right,L,R,val);
    t[h] = max(t[h*2],t[h*2+1]);
}

int get(int h,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return t[h];
    push(h);
    return max(get(left,L,R),get(right,L,R));
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    cin>>n;
    
    for (int i = 1; i <= n; i++)
        cin>>a[i];
        
    go();
    build(1,1,n);
    
    int q;
    cin>>q;
    for (int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        v[l].pb({r,i});
    }
    
    for (int i = n; i >= 1; i--){
        for (auto id: nx[i]){
            // a = i b = id c >= id + id - i
            if (2*id - i <= n) 
                upd(1,1,n,2*id - i,n,a[i] + a[id]);
        }
        for (auto x: v[i])
            ans[x.s] = get(1,1,n,i,x.f);
    }
    
    for (int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}

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