Submission #1320456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320456		maxFedorchuk	Triple Jump (JOI19_jumps)	C++20	100 / 100	803 ms	77624 KiB

jumps

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

const long long MX=5e5+10,INF=1e9;
long long a[MX],ans[MX];

vector < pair < long long , long long > > goodpairs;
long long n;

struct nd
{
    long long mxa;
    long long mxc;
    long long mxabc;
} tree[4*MX];

void smlupd(long long v,long long zn)
{
    tree[v].mxa=max(tree[v].mxa,zn);
    tree[v].mxabc=max(tree[v].mxabc,tree[v].mxc+tree[v].mxa);
}

long long fget(long long v,long long tl,long long tr,long long l,long long r)
{
    if(tr<l || r<tl){
        return 0;
    }

    if(l<=tl && tr<=r){
        return tree[v].mxabc;
    }

    smlupd(v*2,tree[v].mxa);
    smlupd(v*2+1,tree[v].mxa);

    long long mid=(tl+tr)/2;
    return max(fget(v*2,tl,mid,l,r),fget(v*2+1,mid+1,tr,l,r));
}

long long clc(pair < long long , long long > zp)
{
    return fget(1,1,n,zp.first,zp.second);
}

void build(long long v,long long tl,long long tr)
{
    if(tl==tr){
        tree[v].mxc=a[tl];
        return;
    }

    long long mid=(tl+tr)/2;
    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);

    tree[v].mxc=max(tree[v*2].mxc,tree[v*2+1].mxc);
}


void upd(long long v,long long tl,long long tr,long long l,long long r,long long zn)
{
    if(r<tl || tr<l){
        return;
    }

    if(l<=tl && tr<=r){
        smlupd(v,zn);
        return;
    }

    smlupd(v*2,tree[v].mxa);
    smlupd(v*2+1,tree[v].mxa);

    long long mid=(tl+tr)/2;
    upd(v*2,tl,mid,l,r,zn);
    upd(v*2+1,mid+1,tr,l,r,zn);

    tree[v].mxabc=max(tree[v*2].mxabc,tree[v*2+1].mxabc);
}

void fad(pair < long long , long long > pr)
{
    long long va=pr.first;
    long long vb=pr.second;

    if(2*vb-va<=n)
    {
        upd(1,1,n,2*vb-va,n,a[va]+a[vb]);
    }
}

void clcgoodpair()
{
    stack < pair < long long , long long > > st;
    st.push({INF,0});
    for(long long i=1;i<=n;i++){
        while(st.top().first<a[i]){
            st.pop();
        }

        if(st.top().second!=0){
            goodpairs.push_back({st.top().second,i});
        }

        st.push({a[i],i});
    }

    while(!st.empty()){
        st.pop();
    }

    st.push({INF,n+1});
    for(long long i=n;i>=1;i--){
        while(st.top().first<=a[i]){
            st.pop();
        }

        if(st.top().second!=n+1){
            goodpairs.push_back({i,st.top().second});
        }

        st.push({a[i],i});
    }
}

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

    cin>>n;

    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }

    build(1,1,n);

    clcgoodpair();
    
    vector < pair < pair < long long , long long > , long long > > zap;
    long long q;
    cin>>q;

    for(long long i=1;i<=q;i++){
        long long l,r;
        cin>>l>>r;

        zap.push_back({{l,r},i});
    }

    sort(goodpairs.begin(),goodpairs.end());
    reverse(goodpairs.begin(),goodpairs.end());
    goodpairs.push_back({0,0});

    sort(zap.begin(),zap.end());
    reverse(zap.begin(),zap.end());
    zap.push_back({{0,0},0});

    long long ukv=0,ukz=0;
    for(long long i=n;i>=1;i--){
        while(goodpairs[ukv].first==i){
            fad(goodpairs[ukv]);
            ukv++;
        }

        while(zap[ukz].first.first==i){
            ans[zap[ukz].second]=clc(zap[ukz].first);
            ukz++;
        }
    }

    for(long long 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