oj.uz

Submission #220162

# Submission time Handle Problem Language Result Execution time Memory
220162 2020-04-07T07:31:33 Z PeppaPig Triple Jump (JOI19_jumps) C++14
100 / 100
 1191 ms 89080 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1 << 19;

struct item {
    int val, sum, mx;
    item() : val(-1e9), sum(-1e9), mx(-1e9) {}
    item(int val, int sum, int mx) : val(val), sum(sum), mx(mx) {}
    friend item operator+(const item &a, const item &b) {
        item ret;
        ret.val = max(a.val, b.val);
        ret.sum = max(a.sum, b.sum);
        ret.mx = max({a.mx, b.mx, a.sum + b.val});
        return ret;
    }
} t[N << 1];

int n, q;

void update(int x, int k, bool f, int p = 1, int l = 1, int r = n) {
    if(l == r) {
        if(!f) t[p].val = k;
        else t[p].sum = max(t[p].sum, k);
        if(t[p].val != -1e9 && t[p].sum != -1e9) t[p].mx = t[p].val + t[p].sum;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) update(x, k, f, p << 1, l, mid);
    else update(x, k, f, p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

item query(int x, int y, int p = 1, int l = 1, int r = n) {
    if(x <= l && r <= y) return t[p];
    int mid = (l + r) >> 1;
    if(y <= mid) return query(x, y, p << 1, l, mid);
    if(x > mid) return query(x, y, p << 1 | 1, mid + 1, r);
    return query(x, y, p << 1, l, mid) + query(x, y, p << 1 | 1, mid + 1, r);
}

int A[N], ans[N];
vector<int> relevant[N];
vector<pii> Q[N];

int main() {
    scanf("%d", &n);
    vector<int> stk;
    for(int i = 1; i <= n; i++) {
        scanf("%d", A + i);
        while(!stk.empty() && A[stk.back()] <= A[i]) {
            relevant[stk.back()].emplace_back(i);
            stk.pop_back();
        }
        if(!stk.empty()) relevant[stk.back()].emplace_back(i);
        stk.emplace_back(i);
    }

    scanf("%d", &q);
    for(int i = 1, a, b; i <= q; i++) {
        scanf("%d %d", &a, &b);
        Q[a].emplace_back(b, i);
    }
    for(int i = n; i; i--) {
        update(i, A[i], 0);
        for(int x : relevant[i]) if(2 * x - i <= n) 
            update(2 * x - i, A[i] + A[x], 1);
        for(pii p : Q[i]) ans[p.y] = query(i, p.x).mx;
    }
    for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);

    return 0;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
jumps.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A + i);
         ~~~~~^~~~~~~~~~~~~
jumps.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:66: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 26 ms 37248 KB Output is correct
2 Correct 27 ms 37240 KB Output is correct
3 Correct 25 ms 37248 KB Output is correct
4 Correct 25 ms 37248 KB Output is correct
5 Correct 25 ms 37248 KB Output is correct
6 Correct 26 ms 37248 KB Output is correct
7 Correct 25 ms 37248 KB Output is correct
8 Correct 26 ms 37248 KB Output is correct
9 Correct 25 ms 37248 KB Output is correct
10 Correct 27 ms 37248 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37248 KB Output is correct
2 Correct 27 ms 37240 KB Output is correct
3 Correct 25 ms 37248 KB Output is correct
4 Correct 25 ms 37248 KB Output is correct
5 Correct 25 ms 37248 KB Output is correct
6 Correct 26 ms 37248 KB Output is correct
7 Correct 25 ms 37248 KB Output is correct
8 Correct 26 ms 37248 KB Output is correct
9 Correct 25 ms 37248 KB Output is correct
10 Correct 27 ms 37248 KB Output is correct
11 Correct 330 ms 55544 KB Output is correct
12 Correct 341 ms 55584 KB Output is correct
13 Correct 317 ms 55544 KB Output is correct
14 Correct 326 ms 55544 KB Output is correct
15 Correct 335 ms 55544 KB Output is correct
16 Correct 335 ms 54776 KB Output is correct
17 Correct 338 ms 54904 KB Output is correct
18 Correct 333 ms 54776 KB Output is correct
19 Correct 335 ms 55416 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 44664 KB Output is correct
2 Correct 145 ms 44280 KB Output is correct
3 Correct 146 ms 45036 KB Output is correct
4 Correct 226 ms 44664 KB Output is correct
5 Correct 213 ms 44536 KB Output is correct
6 Correct 234 ms 44536 KB Output is correct
7 Correct 217 ms 44664 KB Output is correct
8 Correct 209 ms 44536 KB Output is correct
9 Correct 211 ms 44536 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37248 KB Output is correct
2 Correct 27 ms 37240 KB Output is correct
3 Correct 25 ms 37248 KB Output is correct
4 Correct 25 ms 37248 KB Output is correct
5 Correct 25 ms 37248 KB Output is correct
6 Correct 26 ms 37248 KB Output is correct
7 Correct 25 ms 37248 KB Output is correct
8 Correct 26 ms 37248 KB Output is correct
9 Correct 25 ms 37248 KB Output is correct
10 Correct 27 ms 37248 KB Output is correct
11 Correct 330 ms 55544 KB Output is correct
12 Correct 341 ms 55584 KB Output is correct
13 Correct 317 ms 55544 KB Output is correct
14 Correct 326 ms 55544 KB Output is correct
15 Correct 335 ms 55544 KB Output is correct
16 Correct 335 ms 54776 KB Output is correct
17 Correct 338 ms 54904 KB Output is correct
18 Correct 333 ms 54776 KB Output is correct
19 Correct 335 ms 55416 KB Output is correct
20 Correct 228 ms 44664 KB Output is correct
21 Correct 145 ms 44280 KB Output is correct
22 Correct 146 ms 45036 KB Output is correct
23 Correct 226 ms 44664 KB Output is correct
24 Correct 213 ms 44536 KB Output is correct
25 Correct 234 ms 44536 KB Output is correct
26 Correct 217 ms 44664 KB Output is correct
27 Correct 209 ms 44536 KB Output is correct
28 Correct 211 ms 44536 KB Output is correct
29 Correct 1191 ms 83360 KB Output is correct
30 Correct 962 ms 82776 KB Output is correct
31 Correct 949 ms 84708 KB Output is correct
32 Correct 1164 ms 83424 KB Output is correct
33 Correct 1172 ms 83448 KB Output is correct
34 Correct 1140 ms 81144 KB Output is correct
35 Correct 1152 ms 80888 KB Output is correct
36 Correct 1143 ms 80748 KB Output is correct
37 Correct 1147 ms 82168 KB Output is correct
38 Correct 880 ms 89016 KB Output is correct
39 Correct 891 ms 89080 KB Output is correct
40 Correct 850 ms 85712 KB Output is correct
41 Correct 894 ms 85096 KB Output is correct
42 Correct 887 ms 85204 KB Output is correct
43 Correct 883 ms 87024 KB Output is correct
44 Correct 939 ms 88272 KB Output is correct
45 Correct 952 ms 88292 KB Output is correct
46 Correct 927 ms 85232 KB Output is correct
47 Correct 929 ms 84788 KB Output is correct
48 Correct 929 ms 84728 KB Output is correct
49 Correct 934 ms 87136 KB Output is correct
50 Correct 1036 ms 86480 KB Output is correct
51 Correct 1000 ms 86392 KB Output is correct
52 Correct 987 ms 84192 KB Output is correct
53 Correct 982 ms 83712 KB Output is correct
54 Correct 947 ms 83704 KB Output is correct
55 Correct 955 ms 85476 KB Output is correct