oj.uz

Submission #748753

# Submission time Handle Problem Language Result Execution time Memory
748753 2023-05-26T21:34:15 Z snpmrnhlol Triple Jump (JOI19_jumps) C++17
100 / 100
 1068 ms 67744 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
const int inf = 1e9;
int v[N];
struct query{
    int l,r,id;
}queries[N];
stack <int> v2;
int l[N];
vector <int> upd[N];
int ans[N];
int n;
struct nod{
    int maxx,maxx2,ans;
}seg[4*N];
nod operator+(nod a,nod b){
    return {max(a.maxx,b.maxx),max(a.maxx2,b.maxx2),max(max(a.ans,b.ans),a.maxx2 + b.maxx)};
}
void build(int l,int r,int node = 1){
    if(l == r){
        seg[node] = {v[l],-inf,-inf};
    }else{
        int mij = (l + r)/2;
        build(l,mij,node*2);
        build(mij + 1,r,node*2 + 1);
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
}
void add(int pos,int val,int l = 0,int r = n - 1,int node = 1){
    //if(l == 0 && r == n - 1)cout<<pos<<' '<<val<<'\n';
    if(l == r){
        seg[node].maxx2 = max(seg[node].maxx2,val);
        seg[node].ans = max(seg[node].maxx + seg[node].maxx2,seg[node].ans);
    }else{
        int mij = (l + r)/2;
        if(pos <= mij){
            add(pos,val,l,mij,node*2);
        }else{
            add(pos,val,mij + 1,r,node*2 + 1);
        }
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
}
nod get(int ql,int qr,int l = 0,int r = n - 1,int node = 1){
    //if(l == 0 && r == n - 1)cout<<ql<<' '<<qr<<'\n';
    if(ql <= l && r <= qr){
        //cout<<node<<' '<<seg[node].maxx<<' '<<seg[node].maxx2<<' '<<seg[node].ans<<'\n';
        return seg[node];
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            return get(ql,qr,l,mij,node*2);
        }else if(mij < ql){
            return get(ql,qr,mij + 1,r,node*2 + 1);
        }else{
            return get(ql,mij,l,mij,node*2) + get(mij + 1,qr,mij + 1,r,node*2 + 1);
        }
    }
}
void display(int l = 0,int r = n - 1,int node = 1){
    if(l != r){
        int mij = (l + r)/2;
        display(l,mij,node*2);
        display(mij + 1,r,node*2 + 1);
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
    cout<<l<<' '<<r<<' '<<seg[node].maxx<<' '<<seg[node].maxx2<<' '<<seg[node].ans<<'\n';
}
int main(){
    int i,j,q,p;
    cin>>n;p = n - 1;
    for(i = 0;i < n;i++)cin>>v[i];
    build(0,n - 1);
    //display();
    for(i = 0;i < n;i++){
        ///check
        while(!v2.empty() && v[v2.top()] <= v[i]){
            l[v2.top()] = i;v2.pop();
        }
        ///add
        v2.push(i);
    }
    while(!v2.empty()){
        l[v2.top()] = -1;
        v2.pop();
    }
    for(i = n - 1;i >= 0;i--){
        while(!v2.empty() && v[v2.top()] <= v[i]){
            upd[i].push_back(v2.top());v2.pop();
            //cout<<i<<' '<<v2.top()<<'\n';
        }
        v2.push(i);
    }
    cin>>q;
    for(i = 0;i < q;i++){
        queries[i].id = i;
        cin>>queries[i].l>>queries[i].r;queries[i].l--;queries[i].r--;
    }
    sort(queries,queries + q,[&](query a,query b){
        return a.l > b.l;
    });
    //add(11,124);
    for(i = 0;i < q;i++){
        while(p >= queries[i].l){
            for(auto x:upd[p]){
                if(x + x - p < n){
                    add(x + x - p,v[x] + v[p]);
                }
            }
            if(l[p] != -1 && l[p] + l[p] -  p <= n - 1)add(l[p] + l[p] - p,v[l[p]] + v[p]);
            p--;
        }
        //display();
        ans[queries[i].id] = get(queries[i].l,queries[i].r).ans;
    }
    for(i = 0;i < q;i++)cout<<ans[i]<<'\n';
    return 0;
}
/**
15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
1
3 12
**/

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:71:11: warning: unused variable 'j' [-Wunused-variable]
   71 |     int i,j,q,p;
      |           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12064 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12068 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12088 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12060 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12064 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12068 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12088 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12060 KB Output is correct
11 Correct 389 ms 29904 KB Output is correct
12 Correct 410 ms 29744 KB Output is correct
13 Correct 381 ms 29964 KB Output is correct
14 Correct 392 ms 29892 KB Output is correct
15 Correct 380 ms 29896 KB Output is correct
16 Correct 382 ms 29256 KB Output is correct
17 Correct 386 ms 29132 KB Output is correct
18 Correct 391 ms 29232 KB Output is correct
19 Correct 437 ms 29732 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 23028 KB Output is correct
2 Correct 106 ms 22288 KB Output is correct
3 Correct 113 ms 27724 KB Output is correct
4 Correct 148 ms 24652 KB Output is correct
5 Correct 150 ms 24736 KB Output is correct
6 Correct 131 ms 24044 KB Output is correct
7 Correct 127 ms 24000 KB Output is correct
8 Correct 156 ms 23976 KB Output is correct
9 Correct 145 ms 24352 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12064 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12068 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12088 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12060 KB Output is correct
11 Correct 389 ms 29904 KB Output is correct
12 Correct 410 ms 29744 KB Output is correct
13 Correct 381 ms 29964 KB Output is correct
14 Correct 392 ms 29892 KB Output is correct
15 Correct 380 ms 29896 KB Output is correct
16 Correct 382 ms 29256 KB Output is correct
17 Correct 386 ms 29132 KB Output is correct
18 Correct 391 ms 29232 KB Output is correct
19 Correct 437 ms 29732 KB Output is correct
20 Correct 145 ms 23028 KB Output is correct
21 Correct 106 ms 22288 KB Output is correct
22 Correct 113 ms 27724 KB Output is correct
23 Correct 148 ms 24652 KB Output is correct
24 Correct 150 ms 24736 KB Output is correct
25 Correct 131 ms 24044 KB Output is correct
26 Correct 127 ms 24000 KB Output is correct
27 Correct 156 ms 23976 KB Output is correct
28 Correct 145 ms 24352 KB Output is correct
29 Correct 1068 ms 60152 KB Output is correct
30 Correct 844 ms 54120 KB Output is correct
31 Correct 845 ms 67744 KB Output is correct
32 Correct 929 ms 60228 KB Output is correct
33 Correct 927 ms 60252 KB Output is correct
34 Correct 890 ms 57880 KB Output is correct
35 Correct 871 ms 57504 KB Output is correct
36 Correct 885 ms 57548 KB Output is correct
37 Correct 910 ms 59084 KB Output is correct
38 Correct 812 ms 60216 KB Output is correct
39 Correct 805 ms 60092 KB Output is correct
40 Correct 762 ms 56856 KB Output is correct
41 Correct 779 ms 56452 KB Output is correct
42 Correct 759 ms 56452 KB Output is correct
43 Correct 777 ms 58188 KB Output is correct
44 Correct 826 ms 60236 KB Output is correct
45 Correct 837 ms 60140 KB Output is correct
46 Correct 787 ms 57052 KB Output is correct
47 Correct 772 ms 56600 KB Output is correct
48 Correct 918 ms 56644 KB Output is correct
49 Correct 799 ms 58700 KB Output is correct
50 Correct 866 ms 60236 KB Output is correct
51 Correct 848 ms 60260 KB Output is correct
52 Correct 808 ms 57660 KB Output is correct
53 Correct 833 ms 57392 KB Output is correct
54 Correct 818 ms 57548 KB Output is correct
55 Correct 969 ms 59052 KB Output is correct