oj.uz

Submission #478131

# Submission time Handle Problem Language Result Execution time Memory
478131 2021-10-05T18:55:08 Z nicolaalexandra Triple Jump (JOI19_jumps) C++14
27 / 100
 236 ms 7012 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 6908 KB Output is correct
2 Correct 200 ms 6908 KB Output is correct
3 Correct 159 ms 6852 KB Output is correct
4 Correct 236 ms 7012 KB Output is correct
5 Correct 192 ms 6880 KB Output is correct
6 Correct 181 ms 6248 KB Output is correct
7 Correct 177 ms 6152 KB Output is correct
8 Correct 170 ms 6148 KB Output is correct
9 Correct 185 ms 6468 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -