oj.uz

Submission #397727

# Submission time Handle Problem Language Result Execution time Memory
397727 2021-05-03T01:04:14 Z timmyfeng Triple Jump (JOI19_jumps) C++17
100 / 100
 2115 ms 147880 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500000;

struct segtree {
    segtree *left, *right;
    int first, second, maxi;

    void apply(int x) {
        first = max(first, x);
        maxi = max(maxi, first + second);
    }

    void push() {
        left->apply(first);
        right->apply(first);
    }

    void pull() {
        second = max(left->second, right->second);
        maxi = max({maxi, left->maxi, right->maxi});
    }

    segtree(int l, int r, int *a) {
        first = maxi = INT_MIN;
        if (l == r) {
            second = a[l];
            maxi = first + second;
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m, a);
            right = new segtree(m + 1, r, a);
            pull();
        }
    }

    void update(int a, int b, int x, int l, int r) {
        if (a > b || b < l || r < a) {
            return;
        } else if (a <= l && r <= b) {
            apply(x);
        } else {
            push();
            int m = (l + r) / 2;
            left->update(a, b, x, l, m);
            right->update(a, b, x, m + 1, r);
            pull(); 
        }
    }

    int query(int a, int b, int l, int r) {
        if (b < l || r < a) {
            return INT_MIN;
        } else if (a <= l && r <= b) {
            return maxi;
        } else {
            push();
            int m = (l + r) / 2;
            return max(left->query(a, b, l, m), right->query(a, b, m + 1, r));
        }
    }
};

vector<array<int, 2>> queries[N];
int a[N], order[N], ans[N];
vector<int> pairs[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    iota(order, order + n, 0);
    stable_sort(order, order + n, [&](int i, int j) {
        return a[i] > a[j];
    });

    set<int> indices;
    for (int i = 0; i < n; ++i) {
        auto it = indices.lower_bound(order[i]);

        if (it != indices.end()) {
            pairs[order[i]].push_back(*it);
        }

        if (it != indices.begin()) {
            pairs[*--it].push_back(order[i]);
        }

        indices.insert(order[i]);
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[l - 1].push_back({r - 1, i});
    }

    segtree *maxi = new segtree(0, n - 1, a);

    for (int i = n - 1; i >= 0; --i) {
        for (auto j : pairs[i]) {
            maxi->update(2 * j - i, n - 1, a[i] + a[j], 0, n - 1);
        }

        for (auto [j, k] : queries[i]) {
            ans[k] = maxi->query(i, j, 0, n - 1);
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23756 KB Output is correct
2 Correct 16 ms 23816 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23756 KB Output is correct
5 Correct 16 ms 23828 KB Output is correct
6 Correct 16 ms 23756 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 18 ms 23756 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 17 ms 23756 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23756 KB Output is correct
2 Correct 16 ms 23816 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23756 KB Output is correct
5 Correct 16 ms 23828 KB Output is correct
6 Correct 16 ms 23756 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 18 ms 23756 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 17 ms 23756 KB Output is correct
11 Correct 325 ms 42824 KB Output is correct
12 Correct 320 ms 42860 KB Output is correct
13 Correct 334 ms 42764 KB Output is correct
14 Correct 347 ms 42824 KB Output is correct
15 Correct 345 ms 42856 KB Output is correct
16 Correct 334 ms 42132 KB Output is correct
17 Correct 319 ms 42052 KB Output is correct
18 Correct 328 ms 42176 KB Output is correct
19 Correct 328 ms 42668 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 61768 KB Output is correct
2 Correct 186 ms 61480 KB Output is correct
3 Correct 186 ms 61496 KB Output is correct
4 Correct 409 ms 61776 KB Output is correct
5 Correct 429 ms 61892 KB Output is correct
6 Correct 338 ms 61116 KB Output is correct
7 Correct 372 ms 61000 KB Output is correct
8 Correct 347 ms 61008 KB Output is correct
9 Correct 331 ms 61240 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23756 KB Output is correct
2 Correct 16 ms 23816 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23756 KB Output is correct
5 Correct 16 ms 23828 KB Output is correct
6 Correct 16 ms 23756 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 18 ms 23756 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 17 ms 23756 KB Output is correct
11 Correct 325 ms 42824 KB Output is correct
12 Correct 320 ms 42860 KB Output is correct
13 Correct 334 ms 42764 KB Output is correct
14 Correct 347 ms 42824 KB Output is correct
15 Correct 345 ms 42856 KB Output is correct
16 Correct 334 ms 42132 KB Output is correct
17 Correct 319 ms 42052 KB Output is correct
18 Correct 328 ms 42176 KB Output is correct
19 Correct 328 ms 42668 KB Output is correct
20 Correct 425 ms 61768 KB Output is correct
21 Correct 186 ms 61480 KB Output is correct
22 Correct 186 ms 61496 KB Output is correct
23 Correct 409 ms 61776 KB Output is correct
24 Correct 429 ms 61892 KB Output is correct
25 Correct 338 ms 61116 KB Output is correct
26 Correct 372 ms 61000 KB Output is correct
27 Correct 347 ms 61008 KB Output is correct
28 Correct 331 ms 61240 KB Output is correct
29 Correct 2078 ms 142160 KB Output is correct
30 Correct 1291 ms 141592 KB Output is correct
31 Correct 1293 ms 141588 KB Output is correct
32 Correct 2115 ms 142164 KB Output is correct
33 Correct 2020 ms 142252 KB Output is correct
34 Correct 1880 ms 140000 KB Output is correct
35 Correct 1775 ms 139584 KB Output is correct
36 Correct 1789 ms 139612 KB Output is correct
37 Correct 1769 ms 141116 KB Output is correct
38 Correct 1598 ms 147880 KB Output is correct
39 Correct 1616 ms 147840 KB Output is correct
40 Correct 1321 ms 144532 KB Output is correct
41 Correct 1331 ms 143968 KB Output is correct
42 Correct 1319 ms 144032 KB Output is correct
43 Correct 1349 ms 146012 KB Output is correct
44 Correct 1670 ms 147308 KB Output is correct
45 Correct 1685 ms 147288 KB Output is correct
46 Correct 1377 ms 144200 KB Output is correct
47 Correct 1401 ms 143716 KB Output is correct
48 Correct 1378 ms 143688 KB Output is correct
49 Correct 1411 ms 145712 KB Output is correct
50 Correct 1737 ms 145488 KB Output is correct
51 Correct 1719 ms 145460 KB Output is correct
52 Correct 1526 ms 142860 KB Output is correct
53 Correct 1495 ms 142600 KB Output is correct
54 Correct 1516 ms 142648 KB Output is correct
55 Correct 1511 ms 144468 KB Output is correct