Submission #1253835

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

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll NEGINF = (ll)-4e18;

struct Node {
    // mx1   = maximum A[i] in the segment
    // mx2   = maximum A[i] + A[j] for i<j in the segment
    // mxAdj = maximum A[i] + A[i+1] for adjacent pair in the segment
    // ans   = maximum A[a]+A[b]+A[c] with a<b<c and (b−a) ≤ (c−b) in the segment
    ll mx1, mx2, mxAdj, ans;
    Node()
      : mx1(NEGINF)
      , mx2(NEGINF)
      , mxAdj(NEGINF)
      , ans(NEGINF)
    {}
};

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

// Merge two child‐nodes L and R whose intervals are
// consecutive: [l..mid] and [mid+1..r]
Node mergeNode(const Node &L, const Node &R, int mid) {
    Node res;
    // best single
    res.mx1 = max(L.mx1, R.mx1);
    // best two‐sum (anywhere)
    res.mx2 = max({ L.mx2,
                    R.mx2,
                    L.mx1 + R.mx1 });
    // best adjacent‐pair sum
    // either fully in L, fully in R, or straddling the boundary at mid/mid+1
    res.mxAdj = max({ L.mxAdj,
                      R.mxAdj,
                      A[mid] + A[mid+1] });
    // best triple:
    //  either entirely in L (L.ans)
    //  or entirely in R (R.ans)
    //  or two in L (an adjacent pair anywhere in L)
    //      plus best single in R
    //  or one in L (best single in L)
    //      plus two adjacent in R
    ll cross1 = (L.mxAdj > NEGINF && R.mx1 > NEGINF
                  ? L.mxAdj + R.mx1
                  : NEGINF);
    ll cross2 = (L.mx1  > NEGINF && R.mxAdj > NEGINF
                  ? L.mx1 + R.mxAdj
                  : NEGINF);
    res.ans = max({ L.ans, R.ans, cross1, cross2 });
    return res;
}

// build segment tree on [l..r] at index p
void build(int p, int l, int r) {
    if (l == r) {
        // leaf
        seg[p].mx1   = A[l];
        seg[p].mx2   = NEGINF;
        seg[p].mxAdj = NEGINF;
        seg[p].ans   = NEGINF;
        return;
    }
    int mid = (l + r) >> 1;
    build(p<<1,   l,   mid);
    build(p<<1|1, mid+1, r);
    seg[p] = mergeNode(seg[p<<1], seg[p<<1|1], mid);
}

// query on [ql..qr], node at p covers [l..r]
Node query(int p, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) {
        // completely outside
        return Node();
    }
    if (ql <= l && r <= qr) {
        // fully inside
        return seg[p];
    }
    int mid = (l + r) >> 1;
    Node left  = query(p<<1,   l,   mid, ql, qr);
    Node right = query(p<<1|1, mid+1, r,   ql, qr);
    // if one side is empty, return the other
    if (left.mx1 == NEGINF)  return right;
    if (right.mx1 == NEGINF) return left;
    // otherwise they are contiguous by construction
    return mergeNode(left, right, mid);
}

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.assign(4*(N+1), Node());

    build(1, 1, N);

    cin >> Q;
    while(Q--){
        int L, R;
        cin >> L >> R;
        Node ans_node = query(1, 1, N, L, R);
        // ans_node.ans holds the maximum A[a]+A[b]+A[c]
        // under the constraint a<b<c, (b−a)≤(c−b)
        // in the subarray [L..R].
        cout << ans_node.ans << "\n";
    }

    return 0;
}

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