Submission #1013587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013587		Aiperiii	Triple Jump (JOI19_jumps)	C++14	100 / 100	758 ms	106692 KiB

jumps

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=5e5+5;
int mx[N*4],ans[N*4],add[N*4],a[N];
vector <pair <int,int> > qu[N];
vector <int> ab[N];
void build(int v,int tl,int tr){
    if(tl==tr)mx[v]=a[tl];
    else{
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        mx[v]=max(mx[v*2],mx[v*2+1]);
    }
}
void push(int v,int tl,int tr){
    ans[v]=max(ans[v],add[v]+mx[v]);
    if(tl!=tr){
        add[v*2]=max(add[v*2],add[v]);
        add[v*2+1]=max(add[v*2+1],add[v]);
    }
    add[v]=0;
}
void update(int v,int tl,int tr,int l,int r,int val){
    if(add[v])push(v,tl,tr);
    if(r<tl or tr<l)return;
    if(l<=tl && tr<=r){
        add[v]=val;
        push(v,tl,tr);
        return;
    }
    int tm=(tl+tr)/2;
    update(v*2,tl,tm,l,r,val);
    update(v*2+1,tm+1,tr,l,r,val);
    ans[v]=max(ans[v*2],ans[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
    if(add[v])push(v,tl,tr);
    if(r<tl or tr<l)return 0;
    if(l<=tl && tr<=r)return ans[v];
    int tm=(tl+tr)/2;
    return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
    
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        qu[l].pb({r,i});
    }
    stack <int> st;
    for(int i=n;i>=1;i--){
        while(!st.empty() && a[st.top()]<=a[i]){
            ab[i].pb(st.top());
            st.pop();
        }
        if(!st.empty())ab[i].pb(st.top());
        st.push(i);
    }
    vector <int> res(q);
    for(int l=n;l>=1;l--){
        for(auto b : ab[l]){
            update(1,1,n,b*2-l,n,a[l]+a[b]);
        }
        for(auto x : qu[l]){
            res[x.ss]=get(1,1,n,l,x.ff);
        }
    }
    for(auto x : res)cout<<x<<"\n";
}



/*

 */

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