oj.uz

Submission #848020

# Submission time Handle Problem Language Result Execution time Memory
848020 2023-09-11T03:35:22 Z Tam_theguide Triple Jump (JOI19_jumps) C++14
100 / 100
 867 ms 121056 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
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];

int 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(int &x, int y) {x = max(x, y);}
void upd(int root, int v) {
    cmax(lazy[root], v);
    cmax(tot[root], seg[root] + lazy[root]);
}

void update(int root, int tl, int tr, int l, int r, int v) {
    if (tl > r || tr < l || l > r) 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]);
}

int get(int root, int tl, int tr, int l, int r) {
    if (tl > r || tr < l || l > r) return 0;
    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));
}


signed 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 8 ms 37208 KB Output is correct
2 Correct 7 ms 37208 KB Output is correct
3 Correct 7 ms 37208 KB Output is correct
4 Correct 7 ms 37208 KB Output is correct
5 Correct 7 ms 37208 KB Output is correct
6 Correct 7 ms 37212 KB Output is correct
7 Correct 7 ms 37208 KB Output is correct
8 Correct 7 ms 37208 KB Output is correct
9 Correct 7 ms 37208 KB Output is correct
10 Correct 7 ms 37628 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37208 KB Output is correct
2 Correct 7 ms 37208 KB Output is correct
3 Correct 7 ms 37208 KB Output is correct
4 Correct 7 ms 37208 KB Output is correct
5 Correct 7 ms 37208 KB Output is correct
6 Correct 7 ms 37212 KB Output is correct
7 Correct 7 ms 37208 KB Output is correct
8 Correct 7 ms 37208 KB Output is correct
9 Correct 7 ms 37208 KB Output is correct
10 Correct 7 ms 37628 KB Output is correct
11 Correct 223 ms 62800 KB Output is correct
12 Correct 241 ms 63120 KB Output is correct
13 Correct 223 ms 62800 KB Output is correct
14 Correct 231 ms 62800 KB Output is correct
15 Correct 243 ms 63020 KB Output is correct
16 Correct 242 ms 62120 KB Output is correct
17 Correct 232 ms 62100 KB Output is correct
18 Correct 241 ms 61948 KB Output is correct
19 Correct 248 ms 62740 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 60752 KB Output is correct
2 Correct 74 ms 61260 KB Output is correct
3 Correct 69 ms 59728 KB Output is correct
4 Correct 125 ms 60880 KB Output is correct
5 Correct 124 ms 60976 KB Output is correct
6 Correct 120 ms 60244 KB Output is correct
7 Correct 137 ms 60460 KB Output is correct
8 Correct 121 ms 59984 KB Output is correct
9 Correct 122 ms 60496 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37208 KB Output is correct
2 Correct 7 ms 37208 KB Output is correct
3 Correct 7 ms 37208 KB Output is correct
4 Correct 7 ms 37208 KB Output is correct
5 Correct 7 ms 37208 KB Output is correct
6 Correct 7 ms 37212 KB Output is correct
7 Correct 7 ms 37208 KB Output is correct
8 Correct 7 ms 37208 KB Output is correct
9 Correct 7 ms 37208 KB Output is correct
10 Correct 7 ms 37628 KB Output is correct
11 Correct 223 ms 62800 KB Output is correct
12 Correct 241 ms 63120 KB Output is correct
13 Correct 223 ms 62800 KB Output is correct
14 Correct 231 ms 62800 KB Output is correct
15 Correct 243 ms 63020 KB Output is correct
16 Correct 242 ms 62120 KB Output is correct
17 Correct 232 ms 62100 KB Output is correct
18 Correct 241 ms 61948 KB Output is correct
19 Correct 248 ms 62740 KB Output is correct
20 Correct 126 ms 60752 KB Output is correct
21 Correct 74 ms 61260 KB Output is correct
22 Correct 69 ms 59728 KB Output is correct
23 Correct 125 ms 60880 KB Output is correct
24 Correct 124 ms 60976 KB Output is correct
25 Correct 120 ms 60244 KB Output is correct
26 Correct 137 ms 60460 KB Output is correct
27 Correct 121 ms 59984 KB Output is correct
28 Correct 122 ms 60496 KB Output is correct
29 Correct 794 ms 117848 KB Output is correct
30 Correct 703 ms 118864 KB Output is correct
31 Correct 663 ms 114944 KB Output is correct
32 Correct 813 ms 117912 KB Output is correct
33 Correct 836 ms 117944 KB Output is correct
34 Correct 818 ms 115764 KB Output is correct
35 Correct 862 ms 115320 KB Output is correct
36 Correct 867 ms 115284 KB Output is correct
37 Correct 810 ms 116756 KB Output is correct
38 Correct 625 ms 120400 KB Output is correct
39 Correct 587 ms 120400 KB Output is correct
40 Correct 614 ms 117032 KB Output is correct
41 Correct 602 ms 116512 KB Output is correct
42 Correct 579 ms 116528 KB Output is correct
43 Correct 597 ms 118392 KB Output is correct
44 Correct 656 ms 120756 KB Output is correct
45 Correct 704 ms 120740 KB Output is correct
46 Correct 634 ms 117584 KB Output is correct
47 Correct 662 ms 117184 KB Output is correct
48 Correct 631 ms 117068 KB Output is correct
49 Correct 623 ms 119276 KB Output is correct
50 Correct 710 ms 121056 KB Output is correct
51 Correct 691 ms 120988 KB Output is correct
52 Correct 717 ms 118540 KB Output is correct
53 Correct 710 ms 118064 KB Output is correct
54 Correct 703 ms 118252 KB Output is correct
55 Correct 678 ms 119908 KB Output is correct