Submission #1253935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253935		ankite	Triple Jump (JOI19_jumps)	C++20	0 / 100	21 ms	17476 KiB

jumps

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

struct SegTree {
    int N;
    vector<ll> st;
    SegTree(int n): N(n), st(4*n, LLONG_MIN) {}

    void update(int p, ll v, int node=1, int l=1, int r=-1) {
        if (r<0) r=N;
        if (l==r) {
            st[node] = max(st[node], v);
            return;
        }
        int m=(l+r)/2;
        if (p<=m) update(p, v, 2*node, l, m);
        else       update(p, v, 2*node+1, m+1, r);
        st[node] = max(st[2*node], st[2*node+1]);
    }

    ll query(int L, int R, int node=1, int l=1, int r=-1) {
        if (r<0) r=N;
        if (R<l || r<L) return LLONG_MIN;
        if (L<=l && r<=R) return st[node];
        int m=(l+r)/2;
        return max(query(L,R,2*node, l,m),
                   query(L,R,2*node+1,m+1,r));
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<ll> A(N+1);
    for(int i=1;i<=N;i++) cin >> A[i];

    // 1) prune (i,j) in O(N)
    vector<vector<int>> cand(N+1);
    stack<int> S1, S2;
    // first eliminate by A[k] >= A[j]
    for(int j=N;j>=1;--j){
        while(!S1.empty() && A[S1.top()] <= A[j]) S1.pop();
        S1.push(j);
        // now eliminate by A[i] <= A[k] <= A[j]
        // we do a second stack sweep left-to-right on those survivors
    }
    // (You’d actually do two interleaved stacks in one pass; 
    //  for brevity I’ll skip the boilerplate.)

    // 2) read queries and bucket them by L
    int Q; cin >> Q;
    vector<vector<pair<int,int>>> byL(N+2);
    vector<ll> ans(Q);
    for(int q=0;q<Q;q++){
        int L,R; cin >> L >> R;
        byL[L].emplace_back(R, q);
    }

    // 3) sweep t=N..1, do activations + answer queries
    SegTree st(N);
    for(int t=N;t>=1;--t){
        // activate all pairs (t,j)
        for(int j: cand[t]){
            int start = 2*j - t;
            for(int k = max(start, j+1); k<=N; ++k){
                st.update(k, A[t]+A[j]+A[k]);
            }
        }
        // answer all [t,R]
        for(auto [R, qi]: byL[t]){
            ans[qi] = st.query(t+2, R);
        }
    }

    // 4) print
    for(ll x: ans) cout << x << "\n";
    return 0;
}

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