oj.uz

Submission #333043

# Submission time Handle Problem Language Result Execution time Memory
333043 2020-12-04T10:33:25 Z phathnv Triple Jump (JOI19_jumps) C++11
100 / 100
 1351 ms 88060 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 5e5 + 2;
const int INF = 1e9;

struct segmentTree{
    int n, maxVal[N * 4], lazy[N * 4], maxA[N * 4];
    void build(int id, int l, int r, int a[N]){
        if (l == r){
            maxVal[id] = maxA[id] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, a);
        build(id << 1 | 1, mid + 1, r, a);
        maxVal[id] = max(maxVal[id << 1], maxVal[id << 1 | 1]);
        maxA[id] = max(maxA[id << 1], maxA[id << 1 | 1]);
    }
    void doLazy(int id, int l, int r){
        maxVal[id] = max(maxVal[id], lazy[id] + maxA[id]);
        if (l < r){
            lazy[id << 1] = max(lazy[id << 1], lazy[id]);
            lazy[id << 1 | 1] = max(lazy[id << 1 | 1], lazy[id]);
        }
    }
    void update(int id, int l, int r, int u, int v, int val){
        doLazy(id, l, r);
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            lazy[id] = max(lazy[id], val);
            doLazy(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        maxVal[id] = max(maxVal[id << 1], maxVal[id << 1 | 1]);
    }
    int getMax(int id, int l, int r, int u, int v){
        doLazy(id, l, r);
        if (v < l || r < u)
            return 0;
        if (u <= l && r <= v)
            return maxVal[id];
        int mid = (l + r) >> 1;
        return max(getMax(id << 1, l, mid, u, v), getMax(id << 1 | 1, mid + 1, r, u, v));
    }

    void init(int _n, int a[N]){
        assert(_n > 0);
        n = _n;
        build(1, 1, n, a);
    }
    void update(int l, int r, int val){
        assert(1 <= l && l <= r && r <= n);
        update(1, 1, n, l, r, val);
    }
    int getMax(int l, int r){
        assert(1 <= l && l <= r && r <= n);
        return getMax(1, 1, n, l, r);
    }
} ST;

int n, q, a[N], answer[N];
vector <int> imp[N];
vector <ii> query[N];

void readInput(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    for(int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        query[l].push_back(mp(r, i));
    }
}

void solve(){
    stack <int> st;
    a[n + 1] = INF;
    st.push(n + 1);
    for(int i = n; i >= 1; i--){
        while (a[i] > a[st.top()]){
            imp[i].push_back(st.top());
            st.pop();
        }
        if (st.top() != n + 1)
            imp[i].push_back(st.top());
        st.push(i);
    }

    ST.init(n, a);
    for(int l = n; l >= 1; l--){
        for(int r : imp[l]){
            int k = 2 * r - l;
            if (k <= n)
                ST.update(k, n, a[l] + a[r]);
        }
        for(ii qr : query[l]){
            int r = qr.X;
            int ind = qr.Y;
            answer[ind] = ST.getMax(l, r);
        }
    }
    for(int i = 1; i <= q; i++)
        cout << answer[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    readInput();
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 16 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 16 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct
11 Correct 361 ms 42672 KB Output is correct
12 Correct 352 ms 42604 KB Output is correct
13 Correct 351 ms 42860 KB Output is correct
14 Correct 364 ms 42732 KB Output is correct
15 Correct 355 ms 42732 KB Output is correct
16 Correct 379 ms 42220 KB Output is correct
17 Correct 365 ms 42220 KB Output is correct
18 Correct 375 ms 42064 KB Output is correct
19 Correct 369 ms 42604 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 39148 KB Output is correct
2 Correct 130 ms 39660 KB Output is correct
3 Correct 125 ms 38764 KB Output is correct
4 Correct 208 ms 39276 KB Output is correct
5 Correct 211 ms 39020 KB Output is correct
6 Correct 201 ms 38380 KB Output is correct
7 Correct 221 ms 38332 KB Output is correct
8 Correct 201 ms 38252 KB Output is correct
9 Correct 203 ms 38636 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 16 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct
11 Correct 361 ms 42672 KB Output is correct
12 Correct 352 ms 42604 KB Output is correct
13 Correct 351 ms 42860 KB Output is correct
14 Correct 364 ms 42732 KB Output is correct
15 Correct 355 ms 42732 KB Output is correct
16 Correct 379 ms 42220 KB Output is correct
17 Correct 365 ms 42220 KB Output is correct
18 Correct 375 ms 42064 KB Output is correct
19 Correct 369 ms 42604 KB Output is correct
20 Correct 205 ms 39148 KB Output is correct
21 Correct 130 ms 39660 KB Output is correct
22 Correct 125 ms 38764 KB Output is correct
23 Correct 208 ms 39276 KB Output is correct
24 Correct 211 ms 39020 KB Output is correct
25 Correct 201 ms 38380 KB Output is correct
26 Correct 221 ms 38332 KB Output is correct
27 Correct 201 ms 38252 KB Output is correct
28 Correct 203 ms 38636 KB Output is correct
29 Correct 1351 ms 82284 KB Output is correct
30 Correct 1183 ms 83712 KB Output is correct
31 Correct 1140 ms 81772 KB Output is correct
32 Correct 1346 ms 82284 KB Output is correct
33 Correct 1335 ms 82412 KB Output is correct
34 Correct 1329 ms 80072 KB Output is correct
35 Correct 1334 ms 79724 KB Output is correct
36 Correct 1330 ms 79852 KB Output is correct
37 Correct 1334 ms 81408 KB Output is correct
38 Correct 941 ms 88060 KB Output is correct
39 Correct 938 ms 87968 KB Output is correct
40 Correct 925 ms 84716 KB Output is correct
41 Correct 927 ms 84204 KB Output is correct
42 Correct 919 ms 84204 KB Output is correct
43 Correct 925 ms 85868 KB Output is correct
44 Correct 1004 ms 87416 KB Output is correct
45 Correct 1006 ms 87556 KB Output is correct
46 Correct 985 ms 84076 KB Output is correct
47 Correct 991 ms 83820 KB Output is correct
48 Correct 986 ms 83692 KB Output is correct
49 Correct 1006 ms 85868 KB Output is correct
50 Correct 1092 ms 85228 KB Output is correct
51 Correct 1087 ms 85388 KB Output is correct
52 Correct 1083 ms 82828 KB Output is correct
53 Correct 1088 ms 82540 KB Output is correct
54 Correct 1072 ms 82412 KB Output is correct
55 Correct 1074 ms 84204 KB Output is correct