oj.uz

Submission #146067

# Submission time Handle Problem Language Result Execution time Memory
146067 2019-08-21T19:41:42 Z fedoseevtimofey Triple Jump (JOI19_jumps) C++14
100 / 100
 1435 ms 114856 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int Inf = 2e9;

struct Node {
    int sum, val, mx;
    Node() {
        sum = mx = -Inf;
        val = 0;
    }
    Node operator +(const Node &other) const {
        Node res;
        res.sum = max(sum, other.sum);
        res.val = max(val, other.val);
        res.mx = max(mx, other.mx);
        res.mx = max(res.mx, sum + other.val);
        return res;
    }
};

const int N = 5e5 + 7;
Node t[4 * N];

void build(int l, int r, int v, vector <int> &a) {
    if (l == r) {
        t[v].val = a[l];
    } else {
        int m = (l + r) >> 1;
        build(l, m, 2 * v + 1, a);
        build(m + 1, r, 2 * v + 2, a);
        t[v] = t[2 * v + 1] + t[2 * v + 2];
    }
}

void modify(int ind, int sm, int l, int r, int v) {
    if (l == r) {
        t[v].sum = max(t[v].sum, sm);
        t[v].mx = t[v].val + t[v].sum;
    } else {
        int m = (l + r) >> 1;
        if (ind <= m) modify(ind, sm, l, m, 2 * v + 1);
        else modify(ind, sm, m + 1, r, 2 * v + 2);
        t[v] = t[2 * v + 1] + t[2 * v + 2];
    }
}

Node get(int ql, int qr, int l, int r, int v) {
    if (qr < l || r < ql) return Node();
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) >> 1;
    return get(ql, qr, l, m, 2 * v + 1) + get(ql, qr, m + 1, r, 2 * v + 2);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector <int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    vector <int> L(n, -1), R(n, n);
    vector <pair <int, int>> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && st.back().first < A[i]) st.pop_back();
        if (!st.empty()) L[i] = st.back().second;
        st.push_back({A[i], i});
    }
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && st.back().first <= A[i]) st.pop_back();
        if (!st.empty()) R[i] = st.back().second;
        st.push_back({A[i], i});
    }
    vector <pair <int, int>> intr;
    for (int i = 0; i < n; ++i) {
        int j = L[i];
        if (j != -1) {
            intr.push_back({j, i});
        }
        j = R[i];
        if (j != n) {
            intr.push_back({i, j});
        }
    }
    sort(intr.begin(), intr.end());
    intr.resize(unique(intr.begin(), intr.end()) - intr.begin());
    build(0, n - 1, 0, A);
    vector <vector <int>> who(n);
    for (auto p : intr) {
        who[p.first].push_back(p.second);
    }
    int q;
    cin >> q;
    vector <int> ql(q), qr(q);
    vector <int> ans(q);
    vector <vector <int>> qrs(n);
    for (int i = 0; i < q; ++i) {
        cin >> ql[i] >> qr[i];
        --ql[i], --qr[i];
        qrs[ql[i]].push_back(i);
    }
    for (int i = n - 1; i >= 0; --i) {
        for (int j : who[i]) {
            if (j + j - i < n) {
                modify(j + j - i, A[i] + A[j], 0, n - 1, 0);
            }
        }
        for (int id : qrs[i]) {
            ans[id] = get(ql[id], qr[id], 0, n - 1, 0).mx;
        }
    }
    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 66 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 21 ms 23804 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 21 ms 23800 KB Output is correct
9 Correct 21 ms 23800 KB Output is correct
10 Correct 21 ms 23800 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 21 ms 23804 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 21 ms 23800 KB Output is correct
9 Correct 21 ms 23800 KB Output is correct
10 Correct 21 ms 23800 KB Output is correct
11 Correct 430 ms 38528 KB Output is correct
12 Correct 440 ms 38536 KB Output is correct
13 Correct 429 ms 38648 KB Output is correct
14 Correct 473 ms 38552 KB Output is correct
15 Correct 434 ms 38544 KB Output is correct
16 Correct 447 ms 37880 KB Output is correct
17 Correct 454 ms 38008 KB Output is correct
18 Correct 456 ms 37764 KB Output is correct
19 Correct 451 ms 38496 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 45156 KB Output is correct
2 Correct 150 ms 45008 KB Output is correct
3 Correct 133 ms 45032 KB Output is correct
4 Correct 219 ms 45156 KB Output is correct
5 Correct 235 ms 45152 KB Output is correct
6 Correct 217 ms 45260 KB Output is correct
7 Correct 213 ms 45160 KB Output is correct
8 Correct 213 ms 45260 KB Output is correct
9 Correct 215 ms 45288 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 21 ms 23804 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 21 ms 23800 KB Output is correct
9 Correct 21 ms 23800 KB Output is correct
10 Correct 21 ms 23800 KB Output is correct
11 Correct 430 ms 38528 KB Output is correct
12 Correct 440 ms 38536 KB Output is correct
13 Correct 429 ms 38648 KB Output is correct
14 Correct 473 ms 38552 KB Output is correct
15 Correct 434 ms 38544 KB Output is correct
16 Correct 447 ms 37880 KB Output is correct
17 Correct 454 ms 38008 KB Output is correct
18 Correct 456 ms 37764 KB Output is correct
19 Correct 451 ms 38496 KB Output is correct
20 Correct 217 ms 45156 KB Output is correct
21 Correct 150 ms 45008 KB Output is correct
22 Correct 133 ms 45032 KB Output is correct
23 Correct 219 ms 45156 KB Output is correct
24 Correct 235 ms 45152 KB Output is correct
25 Correct 217 ms 45260 KB Output is correct
26 Correct 213 ms 45160 KB Output is correct
27 Correct 213 ms 45260 KB Output is correct
28 Correct 215 ms 45288 KB Output is correct
29 Correct 1398 ms 108144 KB Output is correct
30 Correct 1184 ms 107492 KB Output is correct
31 Correct 1137 ms 107636 KB Output is correct
32 Correct 1397 ms 108144 KB Output is correct
33 Correct 1380 ms 108128 KB Output is correct
34 Correct 1384 ms 105740 KB Output is correct
35 Correct 1375 ms 105436 KB Output is correct
36 Correct 1367 ms 105676 KB Output is correct
37 Correct 1435 ms 106920 KB Output is correct
38 Correct 1006 ms 114856 KB Output is correct
39 Correct 1006 ms 114776 KB Output is correct
40 Correct 986 ms 111480 KB Output is correct
41 Correct 995 ms 111088 KB Output is correct
42 Correct 980 ms 110940 KB Output is correct
43 Correct 1000 ms 112736 KB Output is correct
44 Correct 1129 ms 114008 KB Output is correct
45 Correct 1091 ms 114136 KB Output is correct
46 Correct 1067 ms 110936 KB Output is correct
47 Correct 1065 ms 110444 KB Output is correct
48 Correct 1087 ms 110604 KB Output is correct
49 Correct 1111 ms 112616 KB Output is correct
50 Correct 1186 ms 111776 KB Output is correct
51 Correct 1198 ms 111836 KB Output is correct
52 Correct 1169 ms 109304 KB Output is correct
53 Correct 1168 ms 109000 KB Output is correct
54 Correct 1154 ms 109248 KB Output is correct
55 Correct 1204 ms 110800 KB Output is correct