oj.uz

Submission #868927

# Submission time Handle Problem Language Result Execution time Memory
868927 2023-11-02T12:44:35 Z rockstar Triple Jump (JOI19_jumps) C++17
100 / 100
 958 ms 136528 KB 
//#pragma GCC optimize("O3,unroll-loops,inline,fast-math")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()
#define int ll

constexpr int INF = numeric_limits<int>::max() / 2;

struct node {
    int c = 0, res = 0;

    node(int a) {
        c = a;
        res = -INF;
    }

    node() {}
};

node operator+(node a, node b) {
    node x;
    x.res = max(a.res, b.res);
    x.c = max(a.c, b.c);
    return x;
}

struct segment_tree {
    vector<node> tree;
    vector<int> maxupd;
    int n;

    segment_tree(vector<int> &a) {
        n = a.size();
        tree.resize(4 * n);
        maxupd.resize(4 * n, -INF);
        build(1, 0, n - 1, a);
    }

    void build(int v, int tl, int tr, vector<int> &a) {
        if (tl == tr) {
            tree[v] = node(a[tl]);
            return;
        }
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm, a);
        build(2 * v + 1, tm + 1, tr, a);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }

    void push(int v, int tl, int tr) {
        if (tl != tr)
            maxupd[v * 2] = max(maxupd[v * 2], maxupd[v]), maxupd[v * 2 + 1] = max(maxupd[v * 2 + 1], maxupd[v]);
        tree[v].res = max(tree[v].res, tree[v].c + maxupd[v]);
    }

    void upd(int v, int tl, int tr, int l, int r, int val) {
        push(v, tl, tr);
        if (r < tl || tr < l)
            return;
        if (l <= tl && tr <= r) {
            maxupd[v] = max(maxupd[v], val);
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        upd(v * 2, tl, tm, l, r, val);
        upd(v * 2 + 1, tm + 1, tr, l, r, val);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }

    int get(int v, int tl, int tr, int l, int r) {
        push(v, tl, tr);
        if (r < tl || tr < l)
            return 0;
        if (l <= tl && tr <= r)
            return tree[v].res;
        int tm = (tl + tr) / 2;
        return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
    }

    void upd(int l, int val) {
        upd(1, 0, n - 1, l, n - 1, val);
    }

    int get(int l, int r) {
        return get(1, 0, n - 1, l, r);
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &i: a)
        cin >> i;
    vector<pair<int, int>> st;
    vector<vector<pair<int, int>>> ab(n);
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && st.back().first <= a[i]) {
            if (2 * i - st.back().second < n)
                ab[st.back().second].push_back({i, st.back().first + a[i]});
            st.pop_back();
        }
        if (!st.empty()) {
            if (2 * i - st.back().second < n)
                ab[st.back().second].push_back({i, st.back().first + a[i]});
        }
        st.push_back({a[i], i});
    }
    int q;
    cin >> q;
    vector<vector<pair<int, int>>> query(n);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        query[l].push_back({r, i});
    }
    segment_tree tr(a);
    vector<int> res(q);
    for (int i = n - 1; i >= 0; --i) {
        for (auto [b, sum]: ab[i])
            tr.upd(2 * b - i, sum);
        for (auto [r, ind] : query[i])
            res[ind] = tr.get(i, r);
    }
    for (int i : res)
        cout << i << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 216 ms 28292 KB Output is correct
12 Correct 206 ms 28244 KB Output is correct
13 Correct 221 ms 28496 KB Output is correct
14 Correct 206 ms 28244 KB Output is correct
15 Correct 248 ms 28588 KB Output is correct
16 Correct 213 ms 27688 KB Output is correct
17 Correct 213 ms 27756 KB Output is correct
18 Correct 208 ms 27476 KB Output is correct
19 Correct 224 ms 28240 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 42204 KB Output is correct
2 Correct 81 ms 37968 KB Output is correct
3 Correct 82 ms 41336 KB Output is correct
4 Correct 144 ms 42224 KB Output is correct
5 Correct 170 ms 42032 KB Output is correct
6 Correct 141 ms 41564 KB Output is correct
7 Correct 142 ms 41452 KB Output is correct
8 Correct 172 ms 41460 KB Output is correct
9 Correct 143 ms 42036 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 216 ms 28292 KB Output is correct
12 Correct 206 ms 28244 KB Output is correct
13 Correct 221 ms 28496 KB Output is correct
14 Correct 206 ms 28244 KB Output is correct
15 Correct 248 ms 28588 KB Output is correct
16 Correct 213 ms 27688 KB Output is correct
17 Correct 213 ms 27756 KB Output is correct
18 Correct 208 ms 27476 KB Output is correct
19 Correct 224 ms 28240 KB Output is correct
20 Correct 146 ms 42204 KB Output is correct
21 Correct 81 ms 37968 KB Output is correct
22 Correct 82 ms 41336 KB Output is correct
23 Correct 144 ms 42224 KB Output is correct
24 Correct 170 ms 42032 KB Output is correct
25 Correct 141 ms 41564 KB Output is correct
26 Correct 142 ms 41452 KB Output is correct
27 Correct 172 ms 41460 KB Output is correct
28 Correct 143 ms 42036 KB Output is correct
29 Correct 923 ms 133272 KB Output is correct
30 Correct 738 ms 123528 KB Output is correct
31 Correct 735 ms 130996 KB Output is correct
32 Correct 958 ms 133452 KB Output is correct
33 Correct 910 ms 133324 KB Output is correct
34 Correct 925 ms 131180 KB Output is correct
35 Correct 911 ms 130904 KB Output is correct
36 Correct 908 ms 130676 KB Output is correct
37 Correct 941 ms 132376 KB Output is correct
38 Correct 675 ms 136016 KB Output is correct
39 Correct 680 ms 135948 KB Output is correct
40 Correct 660 ms 132928 KB Output is correct
41 Correct 691 ms 132432 KB Output is correct
42 Correct 634 ms 132400 KB Output is correct
43 Correct 641 ms 133848 KB Output is correct
44 Correct 712 ms 136400 KB Output is correct
45 Correct 717 ms 136216 KB Output is correct
46 Correct 675 ms 133204 KB Output is correct
47 Correct 727 ms 132792 KB Output is correct
48 Correct 669 ms 132784 KB Output is correct
49 Correct 692 ms 134624 KB Output is correct
50 Correct 745 ms 136444 KB Output is correct
51 Correct 737 ms 136528 KB Output is correct
52 Correct 800 ms 134136 KB Output is correct
53 Correct 724 ms 133716 KB Output is correct
54 Correct 727 ms 133796 KB Output is correct
55 Correct 749 ms 135248 KB Output is correct