oj.uz

Submission #946865

# Submission time Handle Problem Language Result Execution time Memory
946865 2024-03-15T06:51:18 Z hmm789 Triple Jump (JOI19_jumps) C++14
100 / 100
 917 ms 130716 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007

struct node {
    int s, e, m, ab, c, abc, lz;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2, ab = c = abc = 0, lz = -1;
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void prop() {
        if(lz == -1) return;
        ab = max(ab, lz);
        abc = max(abc, ab+c);
        if(s != e) {
            l->lz = max(l->lz, lz);
            r->lz = max(r->lz, lz);
        }
        lz = -1;
    }
    void update(int x, int y, int val) {
        if(x > y) return;
        prop();
        if(x <= s && e <= y) {lz = max(val, lz); return;}
        else if(x > m) r->update(x, y, val);
        else if(y <= m) l->update(x, y, val);
        else l->update(x, y, val), r->update(x, y, val);
        l->prop(); r->prop();
        abc = max(l->abc, r->abc);
    }
    void update2(int x, int val) {
        if(s == e) {c = val; return;}
        else if(x > m) r->update2(x, val);
        else l->update2(x, val);
        c = max(l->c, r->c);
    }
    int rmax(int x, int y) {
        if(x > y) return -INF;
        prop();
        if(x <= s && e <= y) return abc;
        else if(x > m) return r->rmax(x, y);
        else if(y <= m) return l->rmax(x, y);
        else return max(l->rmax(x, y), r->rmax(x, y));
    }
} *root, *root2;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, x, y, idx;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    tuple<int, int, int> qry[q];
    int ans[q];
    for(int i = 0; i < q; i++) {
        cin >> x >> y;
        x--; y--;
        qry[i] = {x, y, i};
    }
    sort(qry, qry+q);
    stack<int> s;
    vector<pair<int, int>> good;
    for(int i = 0; i < n; i++) {
        while(s.size() && a[s.top()] <= a[i]) {
            good.push_back({s.top(), i});
            s.pop();
        }
        if(s.size()) good.push_back({s.top(), i});
        s.push(i);
    }
    sort(good.begin(), good.end());
    int gidx = good.size()-1, qidx = q-1;
    root = new node(0, n-1);
    for(int i = 0; i < n; i++) root->update2(i, a[i]);
    for(int i = n-1; i >= 0; i--) {
        while(gidx >= 0 && good[gidx].first == i) {
            root->update(min(2*good[gidx].second-good[gidx].first, n), n-1, a[good[gidx].first] + a[good[gidx].second]);
            gidx--;
        }
        while(qidx >= 0 && get<0>(qry[qidx]) == i) {
            tie(x, y, idx) = qry[qidx];
            ans[idx] = root->rmax(x, y);
            qidx--;
        }
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 208 ms 26652 KB Output is correct
12 Correct 213 ms 26572 KB Output is correct
13 Correct 207 ms 26704 KB Output is correct
14 Correct 216 ms 26732 KB Output is correct
15 Correct 206 ms 26612 KB Output is correct
16 Correct 212 ms 26072 KB Output is correct
17 Correct 215 ms 26068 KB Output is correct
18 Correct 210 ms 26068 KB Output is correct
19 Correct 210 ms 26588 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 41656 KB Output is correct
2 Correct 99 ms 38732 KB Output is correct
3 Correct 96 ms 39692 KB Output is correct
4 Correct 143 ms 42936 KB Output is correct
5 Correct 146 ms 42284 KB Output is correct
6 Correct 167 ms 42348 KB Output is correct
7 Correct 139 ms 42168 KB Output is correct
8 Correct 143 ms 40372 KB Output is correct
9 Correct 142 ms 42168 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 208 ms 26652 KB Output is correct
12 Correct 213 ms 26572 KB Output is correct
13 Correct 207 ms 26704 KB Output is correct
14 Correct 216 ms 26732 KB Output is correct
15 Correct 206 ms 26612 KB Output is correct
16 Correct 212 ms 26072 KB Output is correct
17 Correct 215 ms 26068 KB Output is correct
18 Correct 210 ms 26068 KB Output is correct
19 Correct 210 ms 26588 KB Output is correct
20 Correct 154 ms 41656 KB Output is correct
21 Correct 99 ms 38732 KB Output is correct
22 Correct 96 ms 39692 KB Output is correct
23 Correct 143 ms 42936 KB Output is correct
24 Correct 146 ms 42284 KB Output is correct
25 Correct 167 ms 42348 KB Output is correct
26 Correct 139 ms 42168 KB Output is correct
27 Correct 143 ms 40372 KB Output is correct
28 Correct 142 ms 42168 KB Output is correct
29 Correct 917 ms 129968 KB Output is correct
30 Correct 737 ms 121944 KB Output is correct
31 Correct 766 ms 126068 KB Output is correct
32 Correct 902 ms 129784 KB Output is correct
33 Correct 887 ms 130504 KB Output is correct
34 Correct 870 ms 127728 KB Output is correct
35 Correct 892 ms 127424 KB Output is correct
36 Correct 858 ms 127224 KB Output is correct
37 Correct 901 ms 128720 KB Output is correct
38 Correct 634 ms 130284 KB Output is correct
39 Correct 605 ms 130128 KB Output is correct
40 Correct 575 ms 126636 KB Output is correct
41 Correct 566 ms 126124 KB Output is correct
42 Correct 586 ms 126796 KB Output is correct
43 Correct 585 ms 127920 KB Output is correct
44 Correct 630 ms 129928 KB Output is correct
45 Correct 624 ms 130364 KB Output is correct
46 Correct 630 ms 126628 KB Output is correct
47 Correct 637 ms 126524 KB Output is correct
48 Correct 621 ms 126372 KB Output is correct
49 Correct 598 ms 128336 KB Output is correct
50 Correct 666 ms 129968 KB Output is correct
51 Correct 701 ms 130716 KB Output is correct
52 Correct 685 ms 127404 KB Output is correct
53 Correct 677 ms 127148 KB Output is correct
54 Correct 657 ms 127180 KB Output is correct
55 Correct 752 ms 128784 KB Output is correct