oj.uz

Submission #330948

# Submission time Handle Problem Language Result Execution time Memory
330948 2020-11-27T00:36:31 Z jungsnow Triple Jump (JOI19_jumps) C++14
100 / 100
 1367 ms 136080 KB 
///refers to Maripium's code
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn = 500100;
const ll inf = 1e18;

struct sta {
    ll pref, ans, suf;
    sta() : pref(-inf), ans(-inf), suf(-inf) {}
    friend sta operator + (const sta &l, const sta &r) {
        sta ans;
        ans.pref = max(l.pref, r.pref);
        ans.suf = max(l.suf, r.suf);
        ans.ans = max({l.ans, r.ans, l.pref + r.suf});
        return ans;
    }
};

ll A[maxn], Ans[maxn];
sta T[maxn << 2];
vector<pair<int, ll>> es[maxn];
vector<pair<int, int>> qs[maxn];

void build(int v, int l, int r) {
    if (l == r) {
        T[v].suf = A[l];
        return;
    }
    int md = (l + r) >> 1;
    build(v << 1, l, md);
    build(v << 1 | 1, md + 1, r);
    T[v] = T[v << 1] + T[v << 1 | 1];
}

void upd(int v, int l, int r, int pos, ll val) {
    if (l == r) {
        T[v].pref = max(T[v].pref, val);
        return;
    }
    int md = (l + r) >> 1;
    if (pos <= md)
        upd(v << 1, l, md, pos, val);
    else
        upd(v << 1 | 1, md + 1, r, pos, val);
    T[v] = T[v << 1] + T[v << 1 | 1];
}

sta get(int v, int l, int r, int L, int R) {
    if (L > r || R < l) return sta();
    if (L <= l && r <= R) {
        return T[v];
    }
    int md = (l + r) >> 1;
    return get(v << 1, l, md, L, R) + get(v << 1 | 1, md + 1, r, L, R);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    stack<int> st;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        while (!st.empty()) {
            int id = 2 * i - st.top() - 1;
            if (id < N) es[st.top()].emplace_back(A[i] + A[st.top()], id);
            if (A[i] < A[st.top()]) break;
            else st.pop();
        }
        st.push(i);
    }
    int Q; cin >> Q;
    for (int l, r, i = 1; i <= Q; ++i) {
        cin >> l >> r;
        qs[l].emplace_back(r, i);
    }
    build(1, 1, N);
    for (int i = N; i >= 1; --i) {
        for (auto e : es[i]) {
            upd(1, 1, N, e.second, e.first);
        }
        for (auto q : qs[i]) {
            Ans[q.second] = get(1, 1, N, i, q.first).ans;
        }
    }
    for (int i = 1; i <= Q; ++i) {
        cout << Ans[i] << '\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70764 KB Output is correct
2 Correct 40 ms 70764 KB Output is correct
3 Correct 41 ms 70764 KB Output is correct
4 Correct 40 ms 70764 KB Output is correct
5 Correct 47 ms 70764 KB Output is correct
6 Correct 41 ms 70764 KB Output is correct
7 Correct 41 ms 70892 KB Output is correct
8 Correct 41 ms 70764 KB Output is correct
9 Correct 40 ms 70912 KB Output is correct
10 Correct 47 ms 70892 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70764 KB Output is correct
2 Correct 40 ms 70764 KB Output is correct
3 Correct 41 ms 70764 KB Output is correct
4 Correct 40 ms 70764 KB Output is correct
5 Correct 47 ms 70764 KB Output is correct
6 Correct 41 ms 70764 KB Output is correct
7 Correct 41 ms 70892 KB Output is correct
8 Correct 41 ms 70764 KB Output is correct
9 Correct 40 ms 70912 KB Output is correct
10 Correct 47 ms 70892 KB Output is correct
11 Correct 407 ms 91804 KB Output is correct
12 Correct 407 ms 91684 KB Output is correct
13 Correct 401 ms 91628 KB Output is correct
14 Correct 405 ms 91628 KB Output is correct
15 Correct 410 ms 91756 KB Output is correct
16 Correct 423 ms 90988 KB Output is correct
17 Correct 410 ms 91104 KB Output is correct
18 Correct 444 ms 91144 KB Output is correct
19 Correct 431 ms 91580 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 84332 KB Output is correct
2 Correct 131 ms 80424 KB Output is correct
3 Correct 136 ms 81260 KB Output is correct
4 Correct 217 ms 84588 KB Output is correct
5 Correct 215 ms 84460 KB Output is correct
6 Correct 214 ms 83820 KB Output is correct
7 Correct 211 ms 83692 KB Output is correct
8 Correct 204 ms 83692 KB Output is correct
9 Correct 214 ms 84120 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70764 KB Output is correct
2 Correct 40 ms 70764 KB Output is correct
3 Correct 41 ms 70764 KB Output is correct
4 Correct 40 ms 70764 KB Output is correct
5 Correct 47 ms 70764 KB Output is correct
6 Correct 41 ms 70764 KB Output is correct
7 Correct 41 ms 70892 KB Output is correct
8 Correct 41 ms 70764 KB Output is correct
9 Correct 40 ms 70912 KB Output is correct
10 Correct 47 ms 70892 KB Output is correct
11 Correct 407 ms 91804 KB Output is correct
12 Correct 407 ms 91684 KB Output is correct
13 Correct 401 ms 91628 KB Output is correct
14 Correct 405 ms 91628 KB Output is correct
15 Correct 410 ms 91756 KB Output is correct
16 Correct 423 ms 90988 KB Output is correct
17 Correct 410 ms 91104 KB Output is correct
18 Correct 444 ms 91144 KB Output is correct
19 Correct 431 ms 91580 KB Output is correct
20 Correct 235 ms 84332 KB Output is correct
21 Correct 131 ms 80424 KB Output is correct
22 Correct 136 ms 81260 KB Output is correct
23 Correct 217 ms 84588 KB Output is correct
24 Correct 215 ms 84460 KB Output is correct
25 Correct 214 ms 83820 KB Output is correct
26 Correct 211 ms 83692 KB Output is correct
27 Correct 204 ms 83692 KB Output is correct
28 Correct 214 ms 84120 KB Output is correct
29 Correct 1367 ms 130284 KB Output is correct
30 Correct 1065 ms 120172 KB Output is correct
31 Correct 1062 ms 122220 KB Output is correct
32 Correct 1257 ms 130284 KB Output is correct
33 Correct 1261 ms 130296 KB Output is correct
34 Correct 1283 ms 128188 KB Output is correct
35 Correct 1240 ms 127980 KB Output is correct
36 Correct 1242 ms 127632 KB Output is correct
37 Correct 1243 ms 129132 KB Output is correct
38 Correct 888 ms 136044 KB Output is correct
39 Correct 897 ms 136080 KB Output is correct
40 Correct 876 ms 132588 KB Output is correct
41 Correct 861 ms 132136 KB Output is correct
42 Correct 888 ms 132204 KB Output is correct
43 Correct 873 ms 133868 KB Output is correct
44 Correct 938 ms 135276 KB Output is correct
45 Correct 933 ms 135276 KB Output is correct
46 Correct 937 ms 132204 KB Output is correct
47 Correct 920 ms 131796 KB Output is correct
48 Correct 915 ms 131820 KB Output is correct
49 Correct 934 ms 133868 KB Output is correct
50 Correct 1030 ms 133524 KB Output is correct
51 Correct 1026 ms 133612 KB Output is correct
52 Correct 1070 ms 131228 KB Output is correct
53 Correct 1018 ms 131004 KB Output is correct
54 Correct 1051 ms 130668 KB Output is correct
55 Correct 1044 ms 132468 KB Output is correct