oj.uz

Submission #1013071

# Submission time Handle Problem Language Result Execution time Memory
1013071 2024-07-03T06:52:27 Z Alihan_8 Triple Jump (JOI19_jumps) C++17
46 / 100
 1872 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int N = 5e5 + 1;

int n;

struct SegTree{
    vector <int> T, add;

    SegTree(){
        T.resize(N * 8);

        add.resize(N * 8);
    }

    void push(int v, int l, int r){
        if ( l != r ){
            chmax(add[v * 2], add[v]);

            chmax(add[v * 2 + 1], add[v]);
        }

        chmax(T[v], add[v]);

        add[v] = 0;
    }

    void upd(int v, int l, int r, int tl, int tr, int x){
        push(v, l, r);

        if ( l > tr or r < tl ){
            return;
        }

        if ( tl <= l && tr >= r ){
            add[v] = x;

            push(v, l, r);

            return;
        }

        int md = (l + r) >> 1;

        upd(v * 2, l, md, tl, tr, x);

        upd(v * 2 + 1, md + 1, r, tl, tr, x);

        T[v] = max(T[v * 2], T[v * 2 + 1]);
    }

    void upd(int l, int r, int x){
        upd(1, 0, 2 * n, l, r, x);
    }

    int get(int v, int l, int r, int x){
        push(v, l, r);

        if ( l > x ){
            return 0;
        }

        if ( r <= x ){
            return T[v];
        }

        int md = (l + r) >> 1;

        return max(get(v * 2, l, md, x), get(v * 2 + 1, md + 1, r, x));
    }

    int get(int x){
        return get(1, 0, n * 2, x);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    vector <int> a(n + 1);

    for ( int i = 1; i <= n; i++ ){
        cin >> a[i];
    }

    auto f = [&](int x, int l, int r){
        int opt = 0;

        if ( x > l ){ // x -> b
            int mx = a[x - 1], j = x - 2;

            for ( int i = x + 1; i <= r; i++ ){
                while ( j >= l && x - j <= i - x ){
                    chmax(mx, a[j]);

                    j--;
                }

                chmax(opt, mx + a[i] + a[x]);
            }
        }

        if ( x + 2 <= r ){ // x -> a
            int mx = a[x + 1], j = x + 2;

            for ( int i = x + 2; i <= r; i++ ){
                while ( j < i && i - j >= j - x ){
                    chmax(mx, a[j]);

                    j++;
                }

                chmax(opt, mx + a[i] + a[x]);
            }
        }

        if ( x - 2 >= l ){ // x -> c
            multiset <int> st{a[x - 1]};

            int j = x - 2;

            for ( int i = x - 1; i > l; i-- ){
                while ( j >= l && i - j <= x - i ){
                    st.insert(a[j]);

                    j--;
                }

                st.erase(st.find(a[i]));

                chmax(opt, *st.rbegin() + a[i] + a[x]);
            }
        }

        return opt;
    };

    int q; cin >> q;

    if ( q == 1 ){
        while ( q-- ){
            int l, r; cin >> l >> r;

            vector <ar<int,2>> b;

            for ( int i = l; i <= r; i++ ){
                b.pb({-a[i], i});
            }

            sort(all(b));

            vector <int> tmp;

            for ( int i = 0; i < min(30LL, (int)b.size()); i++ ){
                tmp.pb(b[i][1]);
            }

            int opt = 0;

            for ( auto &i: tmp ){
                chmax(opt, f(i, l, r));
            }

            cout << opt << ln;
        }
    } else{
        vector <vector<int>> dp(n + 2, vector <int> (n + 2));

        for ( int i = n - 2; i > 0; i-- ){
            int k = i + 1, mx = 0;

            for ( int j = i + 2; j <= n; j++ ){
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

                while ( k < j && k - i <= j - k ){
                    chmax(mx, a[k]);

                    k++;
                }

                chmax(dp[i][j], mx + a[i] + a[j]);
            }
        }

        while ( q-- ){
            int l, r; cin >> l >> r;

            cout << dp[l][r] << ln;
        }
    }


    cout << '\n';
}

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 0 ms 348 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 348 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 0 ms 348 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 247 ms 205904 KB Output is correct
12 Correct 221 ms 206160 KB Output is correct
13 Correct 253 ms 206240 KB Output is correct
14 Correct 224 ms 206164 KB Output is correct
15 Correct 277 ms 206268 KB Output is correct
16 Correct 220 ms 205396 KB Output is correct
17 Correct 229 ms 205396 KB Output is correct
18 Correct 227 ms 205396 KB Output is correct
19 Correct 223 ms 206160 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 9684 KB Output is correct
2 Correct 624 ms 9928 KB Output is correct
3 Correct 31 ms 6868 KB Output is correct
4 Correct 1601 ms 9928 KB Output is correct
5 Correct 1617 ms 10064 KB Output is correct
6 Correct 1872 ms 9760 KB Output is correct
7 Correct 1592 ms 9408 KB Output is correct
8 Correct 1699 ms 8892 KB Output is correct
9 Correct 506 ms 7376 KB Output is correct

Subtask #4
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 0 ms 348 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 247 ms 205904 KB Output is correct
12 Correct 221 ms 206160 KB Output is correct
13 Correct 253 ms 206240 KB Output is correct
14 Correct 224 ms 206164 KB Output is correct
15 Correct 277 ms 206268 KB Output is correct
16 Correct 220 ms 205396 KB Output is correct
17 Correct 229 ms 205396 KB Output is correct
18 Correct 227 ms 205396 KB Output is correct
19 Correct 223 ms 206160 KB Output is correct
20 Correct 761 ms 9684 KB Output is correct
21 Correct 624 ms 9928 KB Output is correct
22 Correct 31 ms 6868 KB Output is correct
23 Correct 1601 ms 9928 KB Output is correct
24 Correct 1617 ms 10064 KB Output is correct
25 Correct 1872 ms 9760 KB Output is correct
26 Correct 1592 ms 9408 KB Output is correct
27 Correct 1699 ms 8892 KB Output is correct
28 Correct 506 ms 7376 KB Output is correct
29 Runtime error 250 ms 524288 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -