Submission #794594

#	Time	Username	Problem	Language	Result	Execution time	Memory
794594		anton	Triple Jump (JOI19_jumps)	C++17	0 / 100	224 ms	18184 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], d[2*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_max(int l, int r, int lt, int rt, int t){
    if(l<=lt && rt<=r){
        return tree[t];
    }
    else if(r<lt|| rt <l){
        return -INF;
    }
    else{
        int mid = (lt+rt)/2;

        return max(get_max(l, r, lt, mid, t*2), get_max(l, r, mid+1,rt, t*2+1)) + d[t];
    }
}

void add(int l, int r, int v, int lt, int rt, int t){
    if(l<=lt && rt<=r){
        d[t]+=v;
        tree[t] +=v;
    }
    else if(r<lt|| rt <l){
        return;
    }
    else{
        int mid = (lt+rt)/2;

        add(l, r, v, lt, mid, t*2);
        add(l, r, v, mid+1,rt, t*2+1);

        tree[t] = max(tree[t*2], tree[t*2+1]) + d[t];
    }
}

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;

    for(int i = 0; i<n; i++){
        A[i]-=INF;
    }

    build(0, n-1, 1);

    for(int i = 0; i<n; i++){
        A[i]+=INF;
    }

    vector<pair<pii, int>> quers;
    vector<int> ans(q);

    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;*/
        quers.push_back(pair<pii, int>(pii(l, r), i));
    }

    sort(c.begin(), c.end());
    sort(quers.begin(), quers.end());

    map<int, int> inters;
    inters.insert(pii(n, INF));
    inters.insert(pii(-1, -INF));

    for(int i = n-1; i>=0; i--){
        while(c.size()>0 && c.back().first>=i){
            pii inter = c.back();
            c.pop_back();
            //cout<<"inter "<<inter.first<<" "<<inter.second<<endl;
            int effect= 2*inter.second - inter.first;
            int value = A[inter.first]+ A[inter.second];

            if(effect>n-1){
                continue;
            }

            auto it = inters.upper_bound(effect);
            if((--it)->second<value){
                //cout<<"valid"<<endl;
                inters.insert(pii(effect, value));
                int cur_val = value -it->second;
                it = ++inters.find(effect);
                while(it!=inters.end()){
                    //cout<<"adding "<<effect<<" "<<(it->first)-1<<" "<<cur_val<<endl;
                    add(effect, (it->first)-1, cur_val, 0, n-1, 1);

                    if(it->second<value){
                        cur_val=value- it->second;
                        effect = it->first;
                        inters.erase(it++);
                    }
                    else{
                        break;
                    }
                } 
            }
        }

        while(quers.size()>0 && quers.back().first.first>=i){
            auto que = quers.back();
            quers.pop_back();
            ans[que.second] = get_max(que.first.first, que.first.second, 0, n-1, 1);
        }
    }

    for(auto e: ans){
        cout<<e<<endl;
    }
}

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