Submission #478274

#	Time	Username	Problem	Language	Result	Execution time	Memory
478274		nicolaalexandra	Triple Jump (JOI19_jumps)	C++14	100 / 100	1568 ms	87860 KiB

jumps

#include <bits/stdc++.h>
#define DIM 500010
#define INF 2000000000
using namespace std;

deque <int> d;
vector <int> events[DIM];
vector <pair<int,int> > qry[DIM];
int v[DIM],ans[DIM];
int n,i,q,x,y,sol;


struct segment_tree{
    int maxi_init; /// maximul din sirul initial
    int maxi;
    int lazy;
} aint[DIM*4];

void build (int nod, int st, int dr){
    aint[nod].maxi = -INF;
    if (st == dr){
        aint[nod].maxi_init = v[st];
        return;
    }

    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    aint[nod].maxi_init = max (aint[nod<<1].maxi_init,aint[(nod<<1)|1].maxi_init);
}

void update_lazy (int nod, int st, int dr){

    if (!aint[nod].lazy)
        return;

    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
        aint[fiu_st].lazy = max (aint[fiu_st].lazy,aint[nod].lazy);
        aint[fiu_st].maxi = max (aint[fiu_st].maxi,aint[nod].lazy + aint[fiu_st].maxi_init);

        aint[fiu_dr].lazy = max (aint[fiu_dr].lazy,aint[nod].lazy);
        aint[fiu_dr].maxi = max (aint[fiu_dr].maxi,aint[nod].lazy + aint[fiu_dr].maxi_init);

    }
    aint[nod].lazy = 0;
}

void update (int nod, int st, int dr, int x, int y, int val){

    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].lazy = max (aint[nod].lazy,val);

        aint[nod].maxi = max (aint[nod].maxi,val + aint[nod].maxi_init);

        update_lazy(nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);

    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    aint[nod].maxi = max (aint[nod<<1].maxi,aint[(nod<<1)|1].maxi);
}

void query (int nod, int st, int dr, int x, int y){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        sol = max (sol,aint[nod].maxi);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>v[i];


    /// aflu perechile bune

    for (i=1;i<=n;i++){
        while (!d.empty() && v[i] >= v[d.back()]){
            events[d.back()].push_back(i);
            d.pop_back();
        }

        if (!d.empty())
            events[d.back()].push_back(i);

        d.push_back(i);
    }

    build (1,1,n);


    cin>>q;
    for (i=1;i<=q;i++){
        cin>>x>>y;
        qry[x].push_back(make_pair(y,i));
    }

    //for (i=1;i<=n;i++)
     //   for (auto it : events[i])
       //     cout<<i<<" "<<it<<"\n";

    build (1,1,n);


    for (i=n;i;i--){

        for (auto it : events[i]){
            int poz_b = it;
            int poz_c = 2 * poz_b - i;
            if (poz_c <= n)
                update (1,1,n,poz_c,n,v[i]+v[poz_b]);
        }

        for (auto it : qry[i]){
            sol = -INF;
            query (1,1,n,i,it.first);
            ans[it.second] = sol;
        }
    }


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