Submission #1253412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253412		ankite	Triple Jump (JOI19_jumps)	C++20	0 / 100	23 ms	20552 KiB

jumps

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

struct Node {
    ll best1, best2, best3;
    // best1 = max A[i]
    // best2 = max A[i]+A[j], i<j
    // best3 = max A[x]+A[y]+A[z], x<y<z, with (y-x) <= (z-y)
};

vector<Node> seg;
int N, Q;
vector<ll> A;

Node merge_node(const Node &L, const Node &R){
    Node U;
    U.best1 = max(L.best1, R.best1);
    U.best2 = max({ L.best2,
                    R.best2,
                    L.best1 + R.best1 });
    U.best3 = max({ L.best3,
                    R.best3,
                    L.best2 + R.best1,
                    L.best1 + R.best2 });
    return U;
}

void build(int idx, int l, int r){
    if(l==r){
        seg[idx] = { A[l], LLONG_MIN/2, LLONG_MIN/2 };
        return;
    }
    int m = (l+r)>>1;
    build(idx<<1, l, m);
    build(idx<<1|1, m+1, r);
    seg[idx] = merge_node(seg[idx<<1], seg[idx<<1|1]);
}

Node query(int idx, int l, int r, int ql, int qr){
    if(ql<=l && r<=qr) return seg[idx];
    int m = (l+r)>>1;
    if(qr<=m) return query(idx<<1, l, m, ql, qr);
    if(ql> m) return query(idx<<1|1, m+1, r, ql, qr);
    Node L = query(idx<<1, l, m, ql, qr);
    Node R = query(idx<<1|1, m+1, r, ql, qr);
    return merge_node(L, R);
}

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

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

    seg.resize(4*(N+1));
    build(1,1,N);

    cin >> Q;
    while(Q--){
        int l, r;
        cin >> l >> r;
        auto ans = query(1,1,N,l,r);
        // If there's no valid triple, best3 will be very negative.
        // You can define what to print in that case; here we print best3 as is.
        cout << ans.best3 << "\n";
    }
    return 0;
}

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