oj.uz

Submission #478274

# Submission time Handle Problem Language Result Execution time Memory
478274 2021-10-06T19:15:48 Z nicolaalexandra Triple Jump (JOI19_jumps) C++14
100 / 100
 1568 ms 87860 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 14 ms 23800 KB Output is correct
3 Correct 12 ms 23736 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 13 ms 23752 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 12 ms 23728 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 14 ms 23800 KB Output is correct
3 Correct 12 ms 23736 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 13 ms 23752 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 12 ms 23728 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 473 ms 42796 KB Output is correct
12 Correct 461 ms 42728 KB Output is correct
13 Correct 469 ms 42668 KB Output is correct
14 Correct 496 ms 42692 KB Output is correct
15 Correct 454 ms 42732 KB Output is correct
16 Correct 448 ms 42108 KB Output is correct
17 Correct 418 ms 42096 KB Output is correct
18 Correct 440 ms 42024 KB Output is correct
19 Correct 434 ms 42540 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 37196 KB Output is correct
2 Correct 161 ms 36996 KB Output is correct
3 Correct 161 ms 37800 KB Output is correct
4 Correct 242 ms 37180 KB Output is correct
5 Correct 266 ms 37316 KB Output is correct
6 Correct 239 ms 37196 KB Output is correct
7 Correct 228 ms 37196 KB Output is correct
8 Correct 237 ms 37276 KB Output is correct
9 Correct 247 ms 37188 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 14 ms 23800 KB Output is correct
3 Correct 12 ms 23736 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 13 ms 23752 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 12 ms 23728 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 473 ms 42796 KB Output is correct
12 Correct 461 ms 42728 KB Output is correct
13 Correct 469 ms 42668 KB Output is correct
14 Correct 496 ms 42692 KB Output is correct
15 Correct 454 ms 42732 KB Output is correct
16 Correct 448 ms 42108 KB Output is correct
17 Correct 418 ms 42096 KB Output is correct
18 Correct 440 ms 42024 KB Output is correct
19 Correct 434 ms 42540 KB Output is correct
20 Correct 242 ms 37196 KB Output is correct
21 Correct 161 ms 36996 KB Output is correct
22 Correct 161 ms 37800 KB Output is correct
23 Correct 242 ms 37180 KB Output is correct
24 Correct 266 ms 37316 KB Output is correct
25 Correct 239 ms 37196 KB Output is correct
26 Correct 228 ms 37196 KB Output is correct
27 Correct 237 ms 37276 KB Output is correct
28 Correct 247 ms 37188 KB Output is correct
29 Correct 1445 ms 82004 KB Output is correct
30 Correct 1349 ms 81532 KB Output is correct
31 Correct 1288 ms 83508 KB Output is correct
32 Correct 1451 ms 82192 KB Output is correct
33 Correct 1568 ms 82064 KB Output is correct
34 Correct 1451 ms 79748 KB Output is correct
35 Correct 1457 ms 79532 KB Output is correct
36 Correct 1447 ms 79428 KB Output is correct
37 Correct 1447 ms 80940 KB Output is correct
38 Correct 1156 ms 87856 KB Output is correct
39 Correct 1169 ms 87860 KB Output is correct
40 Correct 1102 ms 84548 KB Output is correct
41 Correct 1098 ms 83928 KB Output is correct
42 Correct 1128 ms 83888 KB Output is correct
43 Correct 1126 ms 85728 KB Output is correct
44 Correct 1213 ms 87288 KB Output is correct
45 Correct 1189 ms 87176 KB Output is correct
46 Correct 1101 ms 84144 KB Output is correct
47 Correct 1115 ms 83768 KB Output is correct
48 Correct 1106 ms 83684 KB Output is correct
49 Correct 1151 ms 85840 KB Output is correct
50 Correct 1250 ms 85316 KB Output is correct
51 Correct 1257 ms 85284 KB Output is correct
52 Correct 1225 ms 82860 KB Output is correct
53 Correct 1223 ms 82372 KB Output is correct
54 Correct 1205 ms 82412 KB Output is correct
55 Correct 1245 ms 84216 KB Output is correct