Submission #1256870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256870		lastgirl	Triple Jump (JOI19_jumps)	C++20	100 / 100	893 ms	93196 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int MAXN = 500000 + 5;

// dữ liệu
int n, q;
ll A[MAXN];
vector<int> g[MAXN];           // g[i] chứa các j sao cho (i, j) là candidate (lưu khi build)
vector<vector<pair<int,int>>> queries; // queries[L] = vector of (R, idx)
ll ans[MAXN];


struct Seg {
    int N;
    vector<ll> seg, mx, lz;
    Seg(int n=0){ init(n); }
    void init(int n){
        N = 1;
        while(N < n) N <<= 1;
        seg.assign(2*N, (ll)LLONG_MIN/4);
        mx.assign(2*N, (ll)LLONG_MIN/4);
        lz.assign(2*N, 0);
    }
    // build leaves with A[1..n]
    void build(int n){
        for(int i=0;i<n;i++){
            mx[N+i] = A[i+1];
            seg[N+i] = A[i+1]; // initial best_base = 0 => seg = 0 + A[i]
        }
        for(int i=n;i<N;i++){
            mx[N+i] = (ll)LLONG_MIN/4;
            seg[N+i] = (ll)LLONG_MIN/4;
        }
        for(int v=N-1; v>=1; --v){
            mx[v] = max(mx[v<<1], mx[v<<1|1]);
            seg[v] = max(seg[v<<1], seg[v<<1|1]);
        }
    }
    inline void apply_node(int v, ll base){
        // setting best_base = max(best_base, base) implies
        // seg[v] = max(seg[v], base + mx[v])
        if(base == 0) return;
        seg[v] = max(seg[v], base + mx[v]);
        lz[v] = max(lz[v], base);
    }
    inline void push(int v){
        if(v>=N) return;
        if(lz[v]){
            apply_node(v<<1, lz[v]);
            apply_node(v<<1|1, lz[v]);
            lz[v] = 0;
        }
    }
    // update range [L, R] (1-indexed inclusive) with best_base = max(best_base, val)
    void upd_range(int L, int R, ll val){ if(L>R) return; upd_range_impl(L, R, val, 1, 1, N); }
    void upd_range_impl(int L, int R, ll val, int v, int l, int r){
        if(L > r || R < l) return;
        if(L <= l && r <= R){
            apply_node(v, val);
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        upd_range_impl(L, R, val, v<<1, l, m);
        upd_range_impl(L, R, val, v<<1|1, m+1, r);
        seg[v] = max(seg[v<<1], seg[v<<1|1]);
    }
    // query max seg over [L, R] inclusive
    ll query(int L, int R){ if(L>R) return (ll)LLONG_MIN/4; return query_impl(L, R, 1, 1, N); }
    ll query_impl(int L, int R, int v, int l, int r){
        if(L > r || R < l) return (ll)LLONG_MIN/4;
        if(L <= l && r <= R) return seg[v];
        push(v);
        int m = (l + r) >> 1;
        return max(query_impl(L, R, v<<1, l, m), query_impl(L, R, v<<1|1, m+1, r));
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> A[i];

    // build candidate edges g using a monotonic stack approach (as in official solutions)
    // sentinel 0 with very large value
    A[0] = (ll)1e18;
    vector<int> st;
    st.push_back(0);
    for(int i=1;i<=n;i++){
        while(!st.empty() && A[st.back()] <= A[i]){
            g[st.back()].push_back(i);
            st.pop_back();
        }
        g[st.back()].push_back(i);
        st.push_back(i);
    }

    cin >> q;
    queries.assign(n+2, {});
    for(int i=1;i<=q;i++){
        int L,R; cin >> L >> R;
        // note: query will be handled when sweeping i = L
        queries[L].push_back({R, i});
    }

    // segment tree init & build with A values
    Seg seg;
    seg.init(n);
    seg.build(n);

    // sweep i from n down to 1:
    // when at i, for each x in g[i], we add candidate (i, x) which affects all c = k with k >= 2*x - i
    for(int i=n;i>=1;i--){
        for(int x : g[i]){
            // candidate pair (i, x). threshold k0 = 2*x - i
            long long k0 = 2LL * x - i;
            if(k0 <= n){
                // update range [k0..n] best_base = max(best_base, A[i]+A[x])
                seg.upd_range((int)k0, n, A[i] + A[x]);
            }
        }
        // answer queries with L == i:
        for(auto &pr : queries[i]){
            int R = pr.first;
            int idx = pr.second;
            // valid c must satisfy i < b < c <= R and b-a <= c-b -> minimal c is i+2, so c range [i+2..R]
            if(i + 2 <= R){
                ans[idx] = seg.query(i+2, R);
            } else {
                ans[idx] = LLONG_MIN/4; // shouldn't happen because problems ensure L+2 <= R
            }
        }
    }

    for(int i=1;i<=q;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

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