Submission #1253415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253415		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; // max A[i]
    ll best2; // max A[i]+A[j] for i<j
    ll best3; // max A[x]+A[y]+A[z] with x<y<z and (y-x)<= (z-y)
};

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

// Merge two adjacent segments L and R into U
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,  // x,y in L; z in R
                    L.best1 + R.best2   // x in L; y,z in R
                  });
    return U;
}

// Build segment tree over [l..r]
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]);
}

// Query segment tree on [ql..qr]
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 left = query(idx<<1, l, m, ql, qr);
    Node right= query(idx<<1|1, m+1, r, ql, qr);
    return merge_node(left, right);
}

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

    // Input
    cin >> N;
    A.resize(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    cin >> Q;

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

    // Process queries
    while (Q--) {
        int l, r;
        cin >> l >> r;
        Node res = query(1, 1, N, l, r);
        // If no valid triple exists, res.best3 will be very negative.
        cout << res.best3 << "\n";
    }

    return 0;
}

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