Submission #478131

#	Time	Username	Problem	Language	Result	Execution time	Memory
478131		nicolaalexandra	Triple Jump (JOI19_jumps)	C++14	27 / 100	236 ms	7012 KiB

jumps

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

pair <int,int> aint[DIM*4];
int v[DIM];
int n,i,maxi,poz,maxi2,poz2,q,x,y;

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = make_pair(v[st],st);
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    if (aint[nod<<1].first >= aint[(nod<<1)|1].first)
        aint[nod] = aint[nod<<1];
    else aint[nod] = aint[(nod<<1)|1];

}

void query (int nod, int st, int dr, int x, int y, int &maxi, int &poz){
    if (x <= st && dr <= y){
        if (aint[nod].first > maxi){
            maxi = aint[nod].first;
            poz = aint[nod].second;
        }
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y,maxi,poz);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y,maxi,poz);
}

int main (){

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

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

    cin>>q;
    for (;q--;){
        cin>>x>>y;
    }

    build (1,1,n);

    int sol = 0;
    for (i=1;i<=n-2;i++){

        int poz_max_b = (n + i) / 2;

        /// caz 1

        maxi = 0, poz = 0;
        query (1,1,n,i+1,poz_max_b,maxi,poz);

        int sum = v[i] + maxi;

        maxi2 = 0, poz2 = 0;
        query (1,1,n,2*poz-i,n,maxi2,poz2);

        sum += maxi2;

        sol = max (sol,sum);

        /// caz 2

        maxi = 0, poz = 0;
        query (1,1,n,i+2,n,maxi,poz);


        sum = v[i] + maxi;

        maxi2 = 0, poz2 = 0;
        query (1,1,n,i+1,(i+poz)/2,maxi2,poz2);

        sum += maxi2;

        sol = max (sol,sum);
    }

    cout<<sol;


    return 0;
}

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