oj.uz

Submission #242392

# Submission time Handle Problem Language Result Execution time Memory
242392 2020-06-27T15:00:26 Z tqbfjotld Triple Jump (JOI19_jumps) C++14
100 / 100
 1168 ms 99416 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
long long arr[500005];
vector<pair<int,int> > abpairs;
long long ans[500005];
vector<pair<pair<int,int>,int> > queries;

struct node{
    int s,e;
    long long ab,c,abc;
    node *l,*r;
    node(int _s, int _e){
        s = _s;
        e = _e;
        if (s==e){
            c = arr[s];
            ab = -999999999999LL;
            abc = -999999999999LL;
        }
        else{
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
            mergeval();
        }
    }
    void mergeval(){
        if (s==e){
            abc = ab+c;
        }
        else{
            ab = max(l->ab,r->ab);
            c = max(l->c,r->c);
            abc = max(max(l->abc,r->abc),l->ab+r->c);
        }
    }
    void upd(int pos, long long val){
        if (s==e){
            ab = max(ab,val);
        }
        else if (pos>(s+e)/2){
            r->upd(pos,val);
        }
        else{
            l->upd(pos,val);
        }
        mergeval();
    }
    pair<long long,pair<long long,long long> > query(int a, int b){
        if (a<=s && e<=b){
            return {abc,{ab,c}};
        }
        if (b<=(s+e)/2){
            return l->query(a,b);
        }
        if (a>(s+e)/2){
            return r->query(a,b);
        }
        auto lv = l->query(a,b);
        auto rv = r->query(a,b);
        return {max(max(lv.first,rv.first),lv.second.first+rv.second.second),{max(lv.second.first,rv.second.first),max(lv.second.second,rv.second.second)}};
    }
}*root;


int main(){
    scanf("%d",&n);
    for (int x = 0; x<n; x++){
        scanf("%lld",&arr[x]);
    }
    root = new node(0,n+3);
    stack<long long> st;
    for (int x = 0; x<n; x++){
        if (st.empty()){
            st.push(x);
            continue;
        }
        while ((!st.empty()) && arr[x]>=arr[st.top()]){
            abpairs.push_back({st.top(),x});
            st.pop();
        }
        if (!st.empty()){
            abpairs.push_back({st.top(),x});
        }
        st.push(x);
    }

    sort(abpairs.begin(),abpairs.end());

    int q;
    scanf("%d",&q);
    for (int x = 0; x<q; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        a--;b--;
        queries.push_back({{a,b},x});
    }
    sort(queries.begin(),queries.end());
    int c = abpairs.size()-1;
    for (int x = q-1; x>=0; x--){
        while (c>=0 && abpairs[c].first>=queries[x].first.first){
            int pos = abpairs[c].second*2-abpairs[c].first;
            root->upd(min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]);
            //printf("upd %d, %d\n",min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]);
            c--;
        }
        ans[queries[x].second] = root->query(queries[x].first.first,queries[x].first.second).first;
    }
    for (int x = 0; x<q; x++){
        printf("%lld\n",ans[x]);
    }

}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 368 ms 20352 KB Output is correct
12 Correct 349 ms 20364 KB Output is correct
13 Correct 400 ms 20368 KB Output is correct
14 Correct 369 ms 20376 KB Output is correct
15 Correct 368 ms 20284 KB Output is correct
16 Correct 387 ms 19672 KB Output is correct
17 Correct 377 ms 19612 KB Output is correct
18 Correct 397 ms 19712 KB Output is correct
19 Correct 369 ms 20228 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 32872 KB Output is correct
2 Correct 105 ms 30876 KB Output is correct
3 Correct 103 ms 31856 KB Output is correct
4 Correct 154 ms 32872 KB Output is correct
5 Correct 156 ms 32872 KB Output is correct
6 Correct 145 ms 32228 KB Output is correct
7 Correct 147 ms 32104 KB Output is correct
8 Correct 149 ms 32104 KB Output is correct
9 Correct 156 ms 32488 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 368 ms 20352 KB Output is correct
12 Correct 349 ms 20364 KB Output is correct
13 Correct 400 ms 20368 KB Output is correct
14 Correct 369 ms 20376 KB Output is correct
15 Correct 368 ms 20284 KB Output is correct
16 Correct 387 ms 19672 KB Output is correct
17 Correct 377 ms 19612 KB Output is correct
18 Correct 397 ms 19712 KB Output is correct
19 Correct 369 ms 20228 KB Output is correct
20 Correct 154 ms 32872 KB Output is correct
21 Correct 105 ms 30876 KB Output is correct
22 Correct 103 ms 31856 KB Output is correct
23 Correct 154 ms 32872 KB Output is correct
24 Correct 156 ms 32872 KB Output is correct
25 Correct 145 ms 32228 KB Output is correct
26 Correct 147 ms 32104 KB Output is correct
27 Correct 149 ms 32104 KB Output is correct
28 Correct 156 ms 32488 KB Output is correct
29 Correct 1099 ms 99028 KB Output is correct
30 Correct 934 ms 92252 KB Output is correct
31 Correct 952 ms 96460 KB Output is correct
32 Correct 1103 ms 99412 KB Output is correct
33 Correct 1168 ms 99284 KB Output is correct
34 Correct 1123 ms 98516 KB Output is correct
35 Correct 1083 ms 98772 KB Output is correct
36 Correct 1118 ms 98516 KB Output is correct
37 Correct 1079 ms 99272 KB Output is correct
38 Correct 766 ms 99156 KB Output is correct
39 Correct 759 ms 99416 KB Output is correct
40 Correct 729 ms 97748 KB Output is correct
41 Correct 716 ms 97368 KB Output is correct
42 Correct 735 ms 97408 KB Output is correct
43 Correct 793 ms 98004 KB Output is correct
44 Correct 804 ms 98900 KB Output is correct
45 Correct 805 ms 99108 KB Output is correct
46 Correct 786 ms 97524 KB Output is correct
47 Correct 786 ms 97236 KB Output is correct
48 Correct 771 ms 97296 KB Output is correct
49 Correct 776 ms 98516 KB Output is correct
50 Correct 866 ms 98868 KB Output is correct
51 Correct 862 ms 98776 KB Output is correct
52 Correct 847 ms 97664 KB Output is correct
53 Correct 827 ms 97620 KB Output is correct
54 Correct 844 ms 97776 KB Output is correct
55 Correct 847 ms 98412 KB Output is correct