oj.uz

Submission #142540

# Submission time Handle Problem Language Result Execution time Memory
142540 2019-08-09T13:32:22 Z imeimi2000 Triple Jump (JOI19_jumps) C++17
100 / 100
 1289 ms 71860 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;
typedef pair<int, int> pii;

int n, q;
int A[500001];
pair<pii, int> Q[500000];
int ans[500000];
int L[500002];
int R[500002];
vector<int> P[500001];

const int inf = 1e9;

struct node {
    int L, R, LR;
    node() : L(-inf), R(-inf), LR(-inf) {}
    node operator+(const node &p) const {
        node ret = node();
        ret.L = max(L, p.L);
        ret.R = max(R, p.R);
        ret.LR = max({ LR, p.LR, L + p.R });
        return ret;
    }
} seg[1 << 20];

void init(int i, int s, int e) {
    if (s == e) {
        seg[i].R = A[s];
        seg[i].LR = seg[i].L + seg[i].R;
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

void update(int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[i].L = max(seg[i].L, v);
        seg[i].LR = seg[i].L + seg[i].R;
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i << 1, s, m, x, v);
    else update(i << 1 | 1, m + 1, e, x, v);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

node query(int i, int s, int e, int x) {
    if (x < s) return node();
    if (e <= x) return seg[i];
    int m = (s + e) / 2;
    return query(i << 1, s, m, x) + query(i << 1 | 1, m + 1, e, x);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<pii> B;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
        B.emplace_back(A[i], i);
    }
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> Q[i].first.first >> Q[i].first.second;
        Q[i].second = i;
    }
    sort(Q, Q + q);
    sort(B.begin(), B.end());
    for (pii it : B) {
        int i = it.second;
        int l = i, r = i;
        if (L[i - 1] != 0) l = L[i - 1];
        if (R[i + 1] != 0) r = R[i + 1];
        L[l] = L[r] = l;
        R[l] = R[r] = r;
        if (l > 1) P[l - 1].push_back(i);
        if (r < n) P[i].push_back(r + 1);
    }
    init(1, 1, n);
    for (int i = q, j = n + 1; i--; ) {
        int l, r;
        tie(l, r) = Q[i].first;
        while (j > l) {
            for (int k : P[--j]) {
                int x = k + k - j;
                if (x > n) continue;
                int v = A[j] + A[k];
                update(1, 1, n, x, v);
            }
        }
        ans[Q[i].second] = query(1, 1, n, r).LR;
    }
    for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24440 KB Output is correct
2 Correct 23 ms 24440 KB Output is correct
3 Correct 23 ms 24440 KB Output is correct
4 Correct 23 ms 24440 KB Output is correct
5 Correct 24 ms 24444 KB Output is correct
6 Correct 23 ms 24444 KB Output is correct
7 Correct 23 ms 24440 KB Output is correct
8 Correct 23 ms 24440 KB Output is correct
9 Correct 24 ms 24440 KB Output is correct
10 Correct 21 ms 24440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24440 KB Output is correct
2 Correct 23 ms 24440 KB Output is correct
3 Correct 23 ms 24440 KB Output is correct
4 Correct 23 ms 24440 KB Output is correct
5 Correct 24 ms 24444 KB Output is correct
6 Correct 23 ms 24444 KB Output is correct
7 Correct 23 ms 24440 KB Output is correct
8 Correct 23 ms 24440 KB Output is correct
9 Correct 24 ms 24440 KB Output is correct
10 Correct 21 ms 24440 KB Output is correct
11 Correct 385 ms 42360 KB Output is correct
12 Correct 452 ms 42232 KB Output is correct
13 Correct 385 ms 42232 KB Output is correct
14 Correct 390 ms 42232 KB Output is correct
15 Correct 391 ms 42328 KB Output is correct
16 Correct 394 ms 41592 KB Output is correct
17 Correct 398 ms 41592 KB Output is correct
18 Correct 383 ms 41596 KB Output is correct
19 Correct 391 ms 42232 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 36712 KB Output is correct
2 Correct 112 ms 36428 KB Output is correct
3 Correct 112 ms 36388 KB Output is correct
4 Correct 282 ms 36688 KB Output is correct
5 Correct 285 ms 36840 KB Output is correct
6 Correct 246 ms 36072 KB Output is correct
7 Correct 250 ms 35980 KB Output is correct
8 Correct 253 ms 35916 KB Output is correct
9 Correct 256 ms 36328 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24440 KB Output is correct
2 Correct 23 ms 24440 KB Output is correct
3 Correct 23 ms 24440 KB Output is correct
4 Correct 23 ms 24440 KB Output is correct
5 Correct 24 ms 24444 KB Output is correct
6 Correct 23 ms 24444 KB Output is correct
7 Correct 23 ms 24440 KB Output is correct
8 Correct 23 ms 24440 KB Output is correct
9 Correct 24 ms 24440 KB Output is correct
10 Correct 21 ms 24440 KB Output is correct
11 Correct 385 ms 42360 KB Output is correct
12 Correct 452 ms 42232 KB Output is correct
13 Correct 385 ms 42232 KB Output is correct
14 Correct 390 ms 42232 KB Output is correct
15 Correct 391 ms 42328 KB Output is correct
16 Correct 394 ms 41592 KB Output is correct
17 Correct 398 ms 41592 KB Output is correct
18 Correct 383 ms 41596 KB Output is correct
19 Correct 391 ms 42232 KB Output is correct
20 Correct 265 ms 36712 KB Output is correct
21 Correct 112 ms 36428 KB Output is correct
22 Correct 112 ms 36388 KB Output is correct
23 Correct 282 ms 36688 KB Output is correct
24 Correct 285 ms 36840 KB Output is correct
25 Correct 246 ms 36072 KB Output is correct
26 Correct 250 ms 35980 KB Output is correct
27 Correct 253 ms 35916 KB Output is correct
28 Correct 256 ms 36328 KB Output is correct
29 Correct 1289 ms 71524 KB Output is correct
30 Correct 829 ms 70492 KB Output is correct
31 Correct 786 ms 70416 KB Output is correct
32 Correct 1285 ms 71392 KB Output is correct
33 Correct 1281 ms 71356 KB Output is correct
34 Correct 1172 ms 71860 KB Output is correct
35 Correct 1184 ms 71844 KB Output is correct
36 Correct 1214 ms 71648 KB Output is correct
37 Correct 1173 ms 71588 KB Output is correct
38 Correct 1145 ms 70956 KB Output is correct
39 Correct 1161 ms 70976 KB Output is correct
40 Correct 1025 ms 70160 KB Output is correct
41 Correct 1037 ms 70220 KB Output is correct
42 Correct 1030 ms 69728 KB Output is correct
43 Correct 1032 ms 70136 KB Output is correct
44 Correct 1149 ms 70752 KB Output is correct
45 Correct 1145 ms 70520 KB Output is correct
46 Correct 1047 ms 69468 KB Output is correct
47 Correct 1140 ms 69344 KB Output is correct
48 Correct 1049 ms 69156 KB Output is correct
49 Correct 1043 ms 69560 KB Output is correct
50 Correct 1184 ms 69496 KB Output is correct
51 Correct 1206 ms 69600 KB Output is correct
52 Correct 1043 ms 69604 KB Output is correct
53 Correct 1068 ms 69424 KB Output is correct
54 Correct 1063 ms 69064 KB Output is correct
55 Correct 1061 ms 69236 KB Output is correct