oj.uz

Submission #134502

# Submission time Handle Problem Language Result Execution time Memory
134502 2019-07-22T22:56:00 Z RezwanArefin01 Triple Jump (JOI19_jumps) C++17
100 / 100
 1417 ms 111600 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 5e5 + 10;
const ll inf = 1e18;

int n, q, a[N], ans[N];
vector<ii> Q[N]; 
vector<int> B[N]; 

struct Node {
    ll a, f, af; 
    Node(ll a = -inf, ll f = -inf, ll af = -inf): 
        a(a), f(f), af(af) {}
} t[N << 2]; 

Node merge(Node l, Node r) {
    return Node(max(l.a, r.a), max(l.f, r.f), max({l.af, r.af, l.f + r.a}));
}

void update(int node, int l, int r, int i, int x, int f) {
    if(l == r) {
        if(f) t[node].f = max(t[node].f, (ll)x); 
        else t[node].a = max(t[node].a, (ll)x); 
        t[node].af = max(-inf, t[node].f + t[node].a);
    } else {
        int m = l + r >> 1; 
        if(i <= m) update(node << 1, l, m, i, x, f); 
        else update(node << 1 | 1, m + 1, r, i, x, f);
        t[node] = merge(t[node << 1], t[node << 1 | 1]); 
    }
}

Node query(int node, int l, int r, int i, int j) {
    if(r < i || l > j) return Node(); 
    if(i <= l && r <= j) return t[node];
    int m = l + r >> 1; 
    return merge(query(node << 1, l, m, i, j), 
           query(node << 1 | 1, m + 1, r, i, j));
}

int main(int argc, char const *argv[]) {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    scanf("%d", &n);

    stack<int> st;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]); 

        while(st.size() && a[st.top()] <= a[i]) {
            B[st.top()].push_back(i); 
            st.pop();
        }
        if(st.size()) {
            B[st.top()].push_back(i); 
        }
        st.push(i);

        update(1, 1, n, i, a[i], 0);
    }   

    scanf("%d", &q);
    for(int i = 1; i <= q; ++i) {
        int l, r;
        scanf("%d %d", &l, &r); 
        Q[l].emplace_back(r, i);
    }

    for(int i = n; i >= 1; --i) {
        for(int b : B[i]) if(2 * b - i <= n) {
            update(1, 1, n, 2 * b - i, a[i] + a[b], 1);
        }
        for(ii x : Q[i]) {
            ans[x.second] = query(1, 1, n, i, x.first).af; 
        }
    }

    for(int i = 1; i <= q; ++i) {
        printf("%lld\n", ans[i]);
    }
}

Compilation message

jumps.cpp: In function 'void update(int, int, int, int, int, int)':
jumps.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1; 
                 ~~^~~
jumps.cpp: In function 'Node query(int, int, int, int, int)':
jumps.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
jumps.cpp: In function 'int main(int, const char**)':
jumps.cpp:84:32: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
         printf("%lld\n", ans[i]);
                          ~~~~~~^
jumps.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
jumps.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]); 
         ~~~~~^~~~~~~~~~~~~
jumps.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &r); 
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70776 KB Output is correct
2 Correct 61 ms 70776 KB Output is correct
3 Correct 61 ms 70780 KB Output is correct
4 Correct 61 ms 70776 KB Output is correct
5 Correct 61 ms 70776 KB Output is correct
6 Correct 61 ms 70776 KB Output is correct
7 Correct 61 ms 70776 KB Output is correct
8 Correct 61 ms 70776 KB Output is correct
9 Correct 72 ms 70752 KB Output is correct
10 Correct 62 ms 70748 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70776 KB Output is correct
2 Correct 61 ms 70776 KB Output is correct
3 Correct 61 ms 70780 KB Output is correct
4 Correct 61 ms 70776 KB Output is correct
5 Correct 61 ms 70776 KB Output is correct
6 Correct 61 ms 70776 KB Output is correct
7 Correct 61 ms 70776 KB Output is correct
8 Correct 61 ms 70776 KB Output is correct
9 Correct 72 ms 70752 KB Output is correct
10 Correct 62 ms 70748 KB Output is correct
11 Correct 474 ms 84444 KB Output is correct
12 Correct 463 ms 84344 KB Output is correct
13 Correct 470 ms 84344 KB Output is correct
14 Correct 474 ms 84344 KB Output is correct
15 Correct 479 ms 84316 KB Output is correct
16 Correct 478 ms 83640 KB Output is correct
17 Correct 477 ms 83760 KB Output is correct
18 Correct 467 ms 83652 KB Output is correct
19 Correct 498 ms 84280 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 78088 KB Output is correct
2 Correct 180 ms 77816 KB Output is correct
3 Correct 184 ms 78676 KB Output is correct
4 Correct 245 ms 78128 KB Output is correct
5 Correct 242 ms 78020 KB Output is correct
6 Correct 234 ms 78200 KB Output is correct
7 Correct 233 ms 78200 KB Output is correct
8 Correct 233 ms 78072 KB Output is correct
9 Correct 244 ms 78216 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70776 KB Output is correct
2 Correct 61 ms 70776 KB Output is correct
3 Correct 61 ms 70780 KB Output is correct
4 Correct 61 ms 70776 KB Output is correct
5 Correct 61 ms 70776 KB Output is correct
6 Correct 61 ms 70776 KB Output is correct
7 Correct 61 ms 70776 KB Output is correct
8 Correct 61 ms 70776 KB Output is correct
9 Correct 72 ms 70752 KB Output is correct
10 Correct 62 ms 70748 KB Output is correct
11 Correct 474 ms 84444 KB Output is correct
12 Correct 463 ms 84344 KB Output is correct
13 Correct 470 ms 84344 KB Output is correct
14 Correct 474 ms 84344 KB Output is correct
15 Correct 479 ms 84316 KB Output is correct
16 Correct 478 ms 83640 KB Output is correct
17 Correct 477 ms 83760 KB Output is correct
18 Correct 467 ms 83652 KB Output is correct
19 Correct 498 ms 84280 KB Output is correct
20 Correct 277 ms 78088 KB Output is correct
21 Correct 180 ms 77816 KB Output is correct
22 Correct 184 ms 78676 KB Output is correct
23 Correct 245 ms 78128 KB Output is correct
24 Correct 242 ms 78020 KB Output is correct
25 Correct 234 ms 78200 KB Output is correct
26 Correct 233 ms 78200 KB Output is correct
27 Correct 233 ms 78072 KB Output is correct
28 Correct 244 ms 78216 KB Output is correct
29 Correct 1378 ms 106200 KB Output is correct
30 Correct 1201 ms 105216 KB Output is correct
31 Correct 1225 ms 107296 KB Output is correct
32 Correct 1394 ms 106000 KB Output is correct
33 Correct 1377 ms 105804 KB Output is correct
34 Correct 1369 ms 105316 KB Output is correct
35 Correct 1417 ms 105064 KB Output is correct
36 Correct 1358 ms 105244 KB Output is correct
37 Correct 1362 ms 105880 KB Output is correct
38 Correct 994 ms 111536 KB Output is correct
39 Correct 997 ms 111600 KB Output is correct
40 Correct 975 ms 109796 KB Output is correct
41 Correct 986 ms 109656 KB Output is correct
42 Correct 968 ms 109560 KB Output is correct
43 Correct 973 ms 110512 KB Output is correct
44 Correct 1080 ms 110920 KB Output is correct
45 Correct 1074 ms 110936 KB Output is correct
46 Correct 1048 ms 109404 KB Output is correct
47 Correct 1060 ms 109264 KB Output is correct
48 Correct 1045 ms 109244 KB Output is correct
49 Correct 1066 ms 110456 KB Output is correct
50 Correct 1181 ms 109176 KB Output is correct
51 Correct 1171 ms 108940 KB Output is correct
52 Correct 1140 ms 108280 KB Output is correct
53 Correct 1151 ms 108140 KB Output is correct
54 Correct 1180 ms 108040 KB Output is correct
55 Correct 1142 ms 108948 KB Output is correct