Submission #1153535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153535		brover29	Triple Jump (JOI19_jumps)	C++20	100 / 100	1113 ms	179576 KiB

jumps

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=5e5+29;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,q,w[N],st[4*N],z[4*N],lg[N],l[N],r[N],ans[N];
vector<ll>v[N];
vector<pair<ll,ll>>g[N];
ll mx[N][20];
void build(){
    lg[1]=0;
    for(ll i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(ll j=1;j<20;j++){
        ll k=(1ll<<j);
        for(ll i=k-1;i<=n;i++){
            mx[i][j]=max(mx[i][j-1],mx[i-k/2][j-1]);
        }
    }
}
ll get(ll l,ll r){
    ll k=lg[r-l+1];
    return max(mx[r][k],mx[l+(1ll<<k)-1][k]);
}
void push(ll v,ll l,ll r){
    if(!z[v])return;
    ll mid=(r+l)>>1;
    st[v*2]=max(st[v*2],z[v]+get(l,mid));
    st[v*2+1]=max(st[v*2+1],z[v]+get(mid+1,r));
    z[v*2]=max(z[v*2],z[v]);
    z[v*2+1]=max(z[v*2+1],z[v]);
    z[v]=0;
}void upd(ll v,ll l,ll r,ll x,ll y,ll val){
    if(l>y||x>r)return;
    if(x<=l&&r<=y){
        st[v]=max(st[v],val+get(l,r));
        z[v]=max(z[v],val);
        return;
    }
    push(v,l,r);
    ll mid=(r+l)>>1;
    upd(v*2,l,mid,x,y,val);
    upd(v*2+1,mid+1,r,x,y,val);
    st[v]=max(st[v*2],st[v*2+1]);
}ll get(ll v,ll l,ll r,ll x,ll y){
    if(l>y||x>r)return 0;
    if(x<=l&&r<=y)return st[v];
    ll mid=(r+l)>>1;
    push(v,l,r);
    return max(get(v*2,l,mid,x,y),get(v*2+1,mid+1,r,x,y));
}
ll s[N],sz=0;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>w[i];
        mx[i][0]=w[i];
    }ll q;
    cin>>q;
    for(ll i=1;i<=n;i++){
        while(sz&&w[s[sz]]<=w[i]){
            sz--;
        }
        l[i]=s[sz];
        s[++sz]=i;
    }
    sz=0;
    s[sz]=n+1;
    for(ll i=n;i>=1;i--){
        while(sz&&w[s[sz]]<w[i]){
            sz--;
        }
        r[i]=s[sz];
        s[++sz]=i;
    }sz=0;
    build();
    for(ll i=1;i<=n;i++){
        v[i].push_back(r[i]);
        v[l[i]].push_back(i);
    }
    for(ll i=1;i<=q;i++){
        ll L,R,ans=0;
        cin>>L>>R;
        g[L].push_back({R,i});
    }for(ll i=n;i>=1;i--){
        for(auto j:v[i]){
            upd(1,1,n,2*j-i,n,w[i]+w[j]);
        }for(auto [r,id]:g[i]){
            ans[id]=get(1,1,n,i,r);
        }
    }
    for(ll 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