Submission #1013563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013563		Alihan_8	Triple Jump (JOI19_jumps)	C++17	100 / 100	658 ms	129508 KiB

jumps

#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{
    struct Info{
        int opt, mx[2];

        Info(){
            opt = mx[0] = mx[1] = 0;
        };
    };

    Info T[N * 4];

    Info merge(Info L, Info R){
        Info rt;

        for ( auto j: {0, 1} ){
            rt.mx[j] = max(L.mx[j], R.mx[j]);
        }

        rt.opt = max({L.opt, R.opt, L.mx[0] + R.mx[1]});

        return rt;
    }

    void upd(int v, int l, int r, int p, int x, int j){
        if ( l == r ){
            chmax(T[v].mx[j], x);

            chmax(T[v].opt, T[v].mx[0] + T[v].mx[1]);

            return;
        }

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

        if ( p <= md ){
            upd(v * 2, l, md, p, x, j);
        } else{
            upd(v * 2 + 1, md + 1, r, p, x, j);
        }

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

    void upd(int p, int x, int j = 0){
        upd(1, 0, n - 1, p, x, j);
    }

    Info get(int v, int l, int r, int tl, int tr){
        Info ret;

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

        if ( tl <= l && tr >= r ){
            return T[v];
        }

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

        return merge(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
    }

    int query(int l, int r){
        return get(1, 0, n - 1, l, r).opt;
    }
} seg;

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

    cin >> n;

    vector <int> a(n);

    for ( auto &u: a ){
        cin >> u;
    }

    vector <vector<int>> upd(n);

    stack <int> stk;

    for ( int i = 0; i < n; i++ ){
        while ( !stk.empty() && a[stk.top()] < a[i] ){
            stk.pop();
        }

        if ( !stk.empty() ){
            upd[stk.top()].pb(i);
        }

        stk.push(i);
    }

    while ( stk.size() ) stk.pop();

    for ( int i = n - 1; i >= 0; i-- ){
        while ( !stk.empty() && a[stk.top()] < a[i] ){
            stk.pop();
        }

        if ( !stk.empty() ){
            upd[i].pb(stk.top());
        }

        stk.push(i);
    }

    int q; cin >> q;

    vector <vector<ar<int,2>>> qu(n);

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

        --l, --r;

        qu[l].pb({i, r});
    }

    for ( int i = 0; i < n; i++ ){
        seg.upd(i, a[i], 1);
    }

    vector <int> ans(q);

    for ( int i = n - 1; i >= 0; i-- ){
        for ( auto &j: upd[i] ){
            if ( j * 2 - i < n ){
                seg.upd(j * 2 - i, a[i] + a[j]);
            }
        }

        for ( auto &[j, r]: qu[i] ){
            ans[j] = seg.query(i, r);
        }
    }

    for ( auto &u: ans ){
        cout << u << ln;
    }

    cout << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54