oj.uz

Submission #970348

# Submission time Handle Problem Language Result Execution time Memory
970348 2024-04-26T11:42:17 Z efedmrlr Triple Jump (JOI19_jumps) C++17
100 / 100
 436 ms 94684 KB 
#include <bits/stdc++.h>

#define int long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

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

struct Node {
    int ar, f, mx;
    Node() : ar(0), f(0), mx(0) {}
    Node comb(Node &oth) {
        Node ret;
        ret.ar = max(ar, oth.ar);
        ret.f = max(f, oth.f);
        ret.mx = max(mx, oth.mx);
        ret.mx = max(ret.mx, f + oth.ar);
        return ret;
    }
};

struct SegT {
    vector<Node> st;
    int n;
    void reset(int nn) {
        n = nn;
        st.assign(2*(n + 3), Node());
    }
    void build() {
        for(int i = n - 1; i>0; i--) {
            st[i] = st[i << 1].comb(st[(i << 1) | 1]); 
        } 
    }
    void update(int ind, int val) {
        ind += n;
        st[ind].f = max(st[ind].f, val);
        st[ind].mx = max(st[ind].mx, st[ind].f + st[ind].ar);
        for(; ind > 1; ind >>= 1) {
            if(ind & 1) ind ^= 1;
            st[ind >> 1] = st[ind].comb(st[ind | 1]);
        }
    }
    int query(int l, int r) {
        Node lret, rret;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) lret = lret.comb(st[l++]);
            if(r & 1) rret = st[--r].comb(rret);
        }

        return lret.comb(rret).mx;
    }
    int queryc(int l, int r) {
        return query(l, r + 1);
    }
};

int n, q;
vector<int> a;
vector<array<int, 3> > qu;
vector<vector<int> > pr;

void solve() {
    cin >> n;
    a.resize(n + 1);
    for(int i = 1; i<=n; i++) {
        cin >> a[i];
    }
    cin >> q;
    qu.resize(q);
    REP(i, q) {
        cin >> qu[i][0] >> qu[i][1];
        qu[i][2] = i;
    }
    vector<array<int, 2> > stck;
    pr.assign(n + 1, vector<int>());
    for(int i = 1; i<=n; i++) {
        while(stck.size() && stck.back()[0] <= a[i]) {
            pr[stck.back()[1]].pb(i);
            stck.pop_back();
        }
        if(stck.size()) {
            pr[stck.back()[1]].pb(i);
        }
        stck.pb({a[i], i});
    }
    SegT st;
    st.reset(n + 1);
    for(int i = 1; i <= n; i++) {
        st.st[i + st.n].ar = a[i];
    }
    st.build();
    sort(rall(qu));
    vector<int> res(q + 1);
    // for(int i = 1; i <= n; i++) {
    //     for(int j : pr[i]) {
    //         cout << i << " " << j << "\n";
    //     }
    // }
    int cur = n;
    for(auto &c : qu) {
        while(cur > c[0]) {
            cur--;
            for(auto x : pr[cur]) {
                if(2 * x - cur > n) continue;
                st.update(2 * x - cur, a[x] + a[cur]);
            }
        }
        res[c[2]] = st.queryc(c[0], c[1]);
    }

    for(int i = 0; i < q; i++) {
        cout << res[i] << "\n";
    }
}

signed main() {
    fastio();
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 0 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 179 ms 26372 KB Output is correct
12 Correct 181 ms 26196 KB Output is correct
13 Correct 181 ms 26312 KB Output is correct
14 Correct 182 ms 26200 KB Output is correct
15 Correct 182 ms 26192 KB Output is correct
16 Correct 185 ms 25652 KB Output is correct
17 Correct 183 ms 25672 KB Output is correct
18 Correct 183 ms 25468 KB Output is correct
19 Correct 180 ms 26196 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 25172 KB Output is correct
2 Correct 42 ms 24036 KB Output is correct
3 Correct 44 ms 27068 KB Output is correct
4 Correct 70 ms 25172 KB Output is correct
5 Correct 76 ms 25172 KB Output is correct
6 Correct 67 ms 24916 KB Output is correct
7 Correct 66 ms 24396 KB Output is correct
8 Correct 69 ms 24568 KB Output is correct
9 Correct 65 ms 24656 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 179 ms 26372 KB Output is correct
12 Correct 181 ms 26196 KB Output is correct
13 Correct 181 ms 26312 KB Output is correct
14 Correct 182 ms 26200 KB Output is correct
15 Correct 182 ms 26192 KB Output is correct
16 Correct 185 ms 25652 KB Output is correct
17 Correct 183 ms 25672 KB Output is correct
18 Correct 183 ms 25468 KB Output is correct
19 Correct 180 ms 26196 KB Output is correct
20 Correct 66 ms 25172 KB Output is correct
21 Correct 42 ms 24036 KB Output is correct
22 Correct 44 ms 27068 KB Output is correct
23 Correct 70 ms 25172 KB Output is correct
24 Correct 76 ms 25172 KB Output is correct
25 Correct 67 ms 24916 KB Output is correct
26 Correct 66 ms 24396 KB Output is correct
27 Correct 69 ms 24568 KB Output is correct
28 Correct 65 ms 24656 KB Output is correct
29 Correct 421 ms 89940 KB Output is correct
30 Correct 380 ms 86868 KB Output is correct
31 Correct 382 ms 94684 KB Output is correct
32 Correct 427 ms 89776 KB Output is correct
33 Correct 436 ms 89876 KB Output is correct
34 Correct 420 ms 87508 KB Output is correct
35 Correct 413 ms 87176 KB Output is correct
36 Correct 421 ms 87256 KB Output is correct
37 Correct 425 ms 88664 KB Output is correct
38 Correct 356 ms 89936 KB Output is correct
39 Correct 367 ms 89972 KB Output is correct
40 Correct 340 ms 86620 KB Output is correct
41 Correct 334 ms 86100 KB Output is correct
42 Correct 334 ms 86100 KB Output is correct
43 Correct 346 ms 87632 KB Output is correct
44 Correct 337 ms 89848 KB Output is correct
45 Correct 346 ms 89936 KB Output is correct
46 Correct 336 ms 86608 KB Output is correct
47 Correct 337 ms 86404 KB Output is correct
48 Correct 343 ms 86612 KB Output is correct
49 Correct 338 ms 88240 KB Output is correct
50 Correct 365 ms 89936 KB Output is correct
51 Correct 382 ms 89980 KB Output is correct
52 Correct 354 ms 87376 KB Output is correct
53 Correct 349 ms 86984 KB Output is correct
54 Correct 357 ms 87360 KB Output is correct
55 Correct 355 ms 88656 KB Output is correct