oj.uz

Submission #1117326

# Submission time Handle Problem Language Result Execution time Memory
1117326 2024-11-23T10:10:04 Z pacman Triple Jump (JOI19_jumps) C++14
100 / 100
 1680 ms 154952 KB 
#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int maxn = 1e6 + 100;

int n ,Q ,a[maxn], ans[maxn] ,sz = 1;

vector<pair<int ,int>> q[maxn];
vector<int> baze[maxn];


struct segment_tree{
    int seg[maxn * 2], lazy[maxn * 2], maxi[maxn * 2];
    segment_tree(){
        for(int i = 0; i < maxn * 2; i++){
            seg[i] = 0 ,lazy[i] = 0, maxi[i] = 0;
        }
    }

    void build_max(){
        for(int i = sz - 1; i >= 0 ;i--){
            maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]);
        }
    }

    void push(int v, int L, int R){
        if(L == R) return;
        lazy[v * 2] = max(lazy[v * 2], lazy[v]);
        lazy[v * 2 + 1] = max(lazy[v * 2 + 1], lazy[v]);
        seg[v * 2] = max(seg[v * 2], lazy[v] + maxi[v * 2]);
        seg[2 * v + 1] = max(seg[2 * v + 1], lazy[v] + maxi[2 * v + 1]);
        lazy[v] = 0;
    }

    void update(int v ,int L, int R ,int l, int r ,int val){
        if(L > r or l > R){
            return;
        }
        if(L >= l and R <= r){
            seg[v] = max(seg[v] , val + maxi[v]);
            lazy[v] = max(lazy[v], val);
            return;
        }
        push(v ,L, R);
        int mid = (R + L) / 2;
        update(2 * v , L ,mid , l ,r, val);
        update(2 * v + 1, mid + 1 ,R ,l, r, val);
        seg[v] = max(seg[2 * v], seg[2 * v + 1]);
    }

    int get(int v ,int L, int R ,int l, int r ){
        if(L > r or l > R){
            return 0;
        }
        if(l <= L and R <= r){
            return seg[v];
        }
        push(v ,L, R);
        int mid = (R + L) / 2;
        return max(get(2 * v ,L , mid , l, r), get(2 * v + 1 ,mid + 1, R ,l ,r));
    }
}seg;


int32_t main(){

    ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);

    cin >> n;
    while(sz < n) sz *= 2;
    for(int i = 0 ;i < n; i++){
        cin >> a[i];
        seg.maxi[i + sz] = a[i];
    }

    seg.build_max();

    stack<pair<int,int>> s;
    for(int i = 0; i < n; i++){
        while(s.size() and s.top().first < a[i]){
            baze[s.top().second].push_back(i);
            s.pop();
        }
        if(s.size()) baze[s.top().second].push_back(i);
        s.push({a[i], i});
    }

    cin >> Q;
    for(int i = 0 ;i < Q; i++){
        int l, r;
        cin >> l >> r;
        l--,r--;

        q[l].push_back({r, i});
    }

    for(int i = n - 1; i >= 0 ; i--){
        for(auto r : baze[i]){
            int val = a[i] + a[r];
            seg.update(1 , 0, sz - 1, 2 * r - i , n - 1, val);
        }
        for(auto x : q[i]){
            int r = x.first, ind = x.second;
            ans[ind] = seg.get(1 ,0 ,sz - 1 , i, r);
        }
    }

    for(int i = 0 ; i < Q; i++){
        cout << ans[i] << endl;
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94188 KB Output is correct
2 Correct 64 ms 94280 KB Output is correct
3 Correct 69 ms 94288 KB Output is correct
4 Correct 63 ms 94280 KB Output is correct
5 Correct 67 ms 94280 KB Output is correct
6 Correct 67 ms 94232 KB Output is correct
7 Correct 73 ms 94404 KB Output is correct
8 Correct 64 ms 94280 KB Output is correct
9 Correct 67 ms 94192 KB Output is correct
10 Correct 63 ms 94280 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94188 KB Output is correct
2 Correct 64 ms 94280 KB Output is correct
3 Correct 69 ms 94288 KB Output is correct
4 Correct 63 ms 94280 KB Output is correct
5 Correct 67 ms 94280 KB Output is correct
6 Correct 67 ms 94232 KB Output is correct
7 Correct 73 ms 94404 KB Output is correct
8 Correct 64 ms 94280 KB Output is correct
9 Correct 67 ms 94192 KB Output is correct
10 Correct 63 ms 94280 KB Output is correct
11 Correct 932 ms 121560 KB Output is correct
12 Correct 948 ms 121552 KB Output is correct
13 Correct 892 ms 121548 KB Output is correct
14 Correct 919 ms 121496 KB Output is correct
15 Correct 906 ms 121508 KB Output is correct
16 Correct 916 ms 120904 KB Output is correct
17 Correct 946 ms 120880 KB Output is correct
18 Correct 918 ms 120704 KB Output is correct
19 Correct 916 ms 121592 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 105168 KB Output is correct
2 Correct 180 ms 103836 KB Output is correct
3 Correct 151 ms 107080 KB Output is correct
4 Correct 216 ms 105032 KB Output is correct
5 Correct 208 ms 105032 KB Output is correct
6 Correct 213 ms 104436 KB Output is correct
7 Correct 215 ms 104440 KB Output is correct
8 Correct 205 ms 104264 KB Output is correct
9 Correct 204 ms 104520 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94188 KB Output is correct
2 Correct 64 ms 94280 KB Output is correct
3 Correct 69 ms 94288 KB Output is correct
4 Correct 63 ms 94280 KB Output is correct
5 Correct 67 ms 94280 KB Output is correct
6 Correct 67 ms 94232 KB Output is correct
7 Correct 73 ms 94404 KB Output is correct
8 Correct 64 ms 94280 KB Output is correct
9 Correct 67 ms 94192 KB Output is correct
10 Correct 63 ms 94280 KB Output is correct
11 Correct 932 ms 121560 KB Output is correct
12 Correct 948 ms 121552 KB Output is correct
13 Correct 892 ms 121548 KB Output is correct
14 Correct 919 ms 121496 KB Output is correct
15 Correct 906 ms 121508 KB Output is correct
16 Correct 916 ms 120904 KB Output is correct
17 Correct 946 ms 120880 KB Output is correct
18 Correct 918 ms 120704 KB Output is correct
19 Correct 916 ms 121592 KB Output is correct
20 Correct 226 ms 105168 KB Output is correct
21 Correct 180 ms 103836 KB Output is correct
22 Correct 151 ms 107080 KB Output is correct
23 Correct 216 ms 105032 KB Output is correct
24 Correct 208 ms 105032 KB Output is correct
25 Correct 213 ms 104436 KB Output is correct
26 Correct 215 ms 104440 KB Output is correct
27 Correct 205 ms 104264 KB Output is correct
28 Correct 204 ms 104520 KB Output is correct
29 Correct 1604 ms 149856 KB Output is correct
30 Correct 1362 ms 146864 KB Output is correct
31 Correct 1412 ms 154952 KB Output is correct
32 Correct 1572 ms 149832 KB Output is correct
33 Correct 1562 ms 149936 KB Output is correct
34 Correct 1680 ms 147528 KB Output is correct
35 Correct 1553 ms 147272 KB Output is correct
36 Correct 1535 ms 147272 KB Output is correct
37 Correct 1666 ms 148808 KB Output is correct
38 Correct 1365 ms 152392 KB Output is correct
39 Correct 1327 ms 152392 KB Output is correct
40 Correct 1383 ms 149280 KB Output is correct
41 Correct 1320 ms 148596 KB Output is correct
42 Correct 1344 ms 148724 KB Output is correct
43 Correct 1375 ms 150484 KB Output is correct
44 Correct 1399 ms 152680 KB Output is correct
45 Correct 1360 ms 152860 KB Output is correct
46 Correct 1351 ms 149716 KB Output is correct
47 Correct 1362 ms 149236 KB Output is correct
48 Correct 1389 ms 149320 KB Output is correct
49 Correct 1401 ms 151112 KB Output is correct
50 Correct 1454 ms 152928 KB Output is correct
51 Correct 1455 ms 152904 KB Output is correct
52 Correct 1451 ms 150676 KB Output is correct
53 Correct 1393 ms 150164 KB Output is correct
54 Correct 1416 ms 150240 KB Output is correct
55 Correct 1499 ms 151988 KB Output is correct