oj.uz

Submission #853674

# Submission time Handle Problem Language Result Execution time Memory
853674 2023-09-25T01:48:30 Z Tam_theguide Triple Jump (JOI19_jumps) C++14
100 / 100
 782 ms 112012 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;
const int N = 5e5 + 5;
int n, q, a[N], l[N], r[N];
stack<int> st;
using pii = pair<int, int>;
#define fi first
#define se second

vector<pii> query_l[N];
vector<int> being_i[N];

ll tot[4*N], seg[4*N], lazy[4*N], res[N];

void build(int root, int tl, int tr) {
    lazy[root] = -INF;
    if (tl == tr) {
        seg[root] = a[tl];
        tot[root] = seg[root] + lazy[root];
        return;
    }

    int tm = (tl + tr) / 2;
    build(2*root, tl, tm);
    build(2*root+1, tm+1, tr);
    seg[root] = max(seg[2*root], seg[2*root+1]);
    tot[root] = max(tot[2*root], tot[2*root+1]);
}

void cmax(ll &x, ll y) {x = max(x, y);}
void upd(int root, ll v) {
    cmax(lazy[root], v);
    cmax(tot[root], seg[root] + lazy[root]);
}

void update(int root, int tl, int tr, int l, int r, ll v) {
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
        upd(root, v);
        return;
    }

    int tm = (tl + tr) / 2;
    upd(2*root, lazy[root]);
    upd(2*root+1, lazy[root]);
    update(2*root, tl, tm, l, r, v);
    update(2*root+1, tm+1, tr, l, r, v);
    tot[root] = max(tot[2*root], tot[2*root+1]);
}

ll get(int root, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return 0LL;
    if (tl >= l && tr <= r) return tot[root];

    int tm = (tl + tr) / 2;
    upd(2*root, lazy[root]);
    upd(2*root+1, lazy[root]);
    return max(get(2*root, tl, tm, l, r),
               get(2*root+1, tm+1, tr, l, r));
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("triple.inp", "r", stdin);
    //freopen("triple.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        l[i] = 0, r[i] = n+1;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) l[i] = st.top();
        st.push(i);
    }

    while (!st.empty()) st.pop();

    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) r[i] = st.top();
        st.push(i);
    }

    for (int i = 1; i <= n; i++) {
        if (l[i] > 0) being_i[l[i]].push_back(i);
        if (r[i] < n+1) being_i[i].push_back(r[i]);
    }

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        query_l[x].emplace_back(y, i);
    }

    build(1, 1, n);
    for (int i = n; i >= 1; i--) {
        for (auto c: being_i[i]) {
            update(1, 1, n, 2*c - i, n, a[c] + a[i]);
        }
        for (auto c: query_l[i]) {
            res[c.se] = get(1, 1, n, i, c.fi);
        }
    }

    for (int i = 1; i <= q; i++) cout << res[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37208 KB Output is correct
2 Correct 7 ms 37380 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 7 ms 37212 KB Output is correct
5 Correct 7 ms 37208 KB Output is correct
6 Correct 7 ms 37212 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 7 ms 37376 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37208 KB Output is correct
2 Correct 7 ms 37380 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 7 ms 37212 KB Output is correct
5 Correct 7 ms 37208 KB Output is correct
6 Correct 7 ms 37212 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 7 ms 37376 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 225 ms 56272 KB Output is correct
12 Correct 225 ms 56236 KB Output is correct
13 Correct 224 ms 56404 KB Output is correct
14 Correct 222 ms 56428 KB Output is correct
15 Correct 220 ms 56292 KB Output is correct
16 Correct 220 ms 55740 KB Output is correct
17 Correct 220 ms 55672 KB Output is correct
18 Correct 220 ms 55496 KB Output is correct
19 Correct 218 ms 56148 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 57908 KB Output is correct
2 Correct 72 ms 58460 KB Output is correct
3 Correct 70 ms 57728 KB Output is correct
4 Correct 121 ms 57812 KB Output is correct
5 Correct 123 ms 57940 KB Output is correct
6 Correct 121 ms 57172 KB Output is correct
7 Correct 121 ms 56916 KB Output is correct
8 Correct 128 ms 57152 KB Output is correct
9 Correct 119 ms 57488 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37208 KB Output is correct
2 Correct 7 ms 37380 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 7 ms 37212 KB Output is correct
5 Correct 7 ms 37208 KB Output is correct
6 Correct 7 ms 37212 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 7 ms 37376 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 225 ms 56272 KB Output is correct
12 Correct 225 ms 56236 KB Output is correct
13 Correct 224 ms 56404 KB Output is correct
14 Correct 222 ms 56428 KB Output is correct
15 Correct 220 ms 56292 KB Output is correct
16 Correct 220 ms 55740 KB Output is correct
17 Correct 220 ms 55672 KB Output is correct
18 Correct 220 ms 55496 KB Output is correct
19 Correct 218 ms 56148 KB Output is correct
20 Correct 123 ms 57908 KB Output is correct
21 Correct 72 ms 58460 KB Output is correct
22 Correct 70 ms 57728 KB Output is correct
23 Correct 121 ms 57812 KB Output is correct
24 Correct 123 ms 57940 KB Output is correct
25 Correct 121 ms 57172 KB Output is correct
26 Correct 121 ms 56916 KB Output is correct
27 Correct 128 ms 57152 KB Output is correct
28 Correct 119 ms 57488 KB Output is correct
29 Correct 755 ms 106312 KB Output is correct
30 Correct 665 ms 107784 KB Output is correct
31 Correct 673 ms 105964 KB Output is correct
32 Correct 773 ms 106320 KB Output is correct
33 Correct 771 ms 106224 KB Output is correct
34 Correct 774 ms 104064 KB Output is correct
35 Correct 782 ms 103568 KB Output is correct
36 Correct 774 ms 103684 KB Output is correct
37 Correct 771 ms 105412 KB Output is correct
38 Correct 579 ms 111988 KB Output is correct
39 Correct 578 ms 112012 KB Output is correct
40 Correct 571 ms 108624 KB Output is correct
41 Correct 563 ms 108120 KB Output is correct
42 Correct 561 ms 108028 KB Output is correct
43 Correct 565 ms 110012 KB Output is correct
44 Correct 637 ms 111356 KB Output is correct
45 Correct 620 ms 111392 KB Output is correct
46 Correct 594 ms 108472 KB Output is correct
47 Correct 605 ms 107860 KB Output is correct
48 Correct 588 ms 107856 KB Output is correct
49 Correct 608 ms 109908 KB Output is correct
50 Correct 653 ms 109504 KB Output is correct
51 Correct 658 ms 109548 KB Output is correct
52 Correct 633 ms 107092 KB Output is correct
53 Correct 665 ms 106608 KB Output is correct
54 Correct 672 ms 106520 KB Output is correct
55 Correct 650 ms 108632 KB Output is correct