Submission #794428

#	Time	Username	Problem	Language	Result	Execution time	Memory
794428		anton	Triple Jump (JOI19_jumps)	C++17	32 / 100	4062 ms	14204 KiB

jumps

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


const int MAX_N = 5*1e5;
const int INF = 1e18;
int n, q;
int A[MAX_N], tree[4*MAX_N];

void build(int lt, int rt, int t){
    if(lt == rt){
        tree[t] = A[lt];
    }
    else{
        int mid = (lt+rt)/2;

        build(lt, mid, t*2);
        build(mid+1, rt, t*2+1);
        tree[t] = max(tree[t*2], tree[t*2+1]);
    }
}

int get(int l, int r, int lt, int rt, int t){
    if(l<=lt && rt<=r){
        return tree[t];
    }
    else if(rt<l || r<lt){
        return -INF;
    }
    else{
        int mid = (lt + rt)/2;

        return max(get(l, r, lt, mid, t*2), get(l, r, mid+1, rt, t*2+1));
    }
}

int get(int l, int r){
    if(l>r){
        return -INF;
    }
    else{
        l = max(l, 0LL);
        r = min(r, n-1);

        //cout<<"getting "<<l<<" "<<r<<" "<<get(l, r, 0, n-1, 1)<<endl;
        return get(l, r, 0, n-1, 1);
    }
}

signed main(){
    cin>>n;
    for(int i = 0; i<n; i++){
        cin>>A[i];
    }

    vector<pii> st;
    vector<pii> c;

    for(int i= 0; i<n; i++){
        while(st.size()>0 && st.back().second<A[i]){
            c.push_back(pii(st.back().first, i));
            st.pop_back();
        }

        if(st.size()>=1){
            c.push_back(pii(st[st.size()-1].first, i));
        }

        st.push_back(pii(i, A[i]));
    }

    cin>>q;

    build(0, n-1, 1);

    for(int i = 0; i<q; i++){
        int l, r;
        cin>>l>>r;
        l--;
        r--;
        int res= 0;

        for(auto [a, b]: c){
            if(a>=l){
                //cout<<a<<" "<<b<<endl;
                int d = b-a;
                res = max(res, A[a]+A[b]+get(b+d, r));
            }
        }

        cout<<res<<endl;
    }
}

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