Submission #1253831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253831		ankite	Triple Jump (JOI19_jumps)	C++20	0 / 100	213 ms	298652 KiB

jumps

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

struct Node {
    ll best;        // best triple A[a]+A[b]+A[c]
    ll mx;          // max A[x]
    vector<ll> L;   // L[d] = best A[a]+A[a+d] in left half
    vector<ll> R;   // R[d] = best A[c-d]+A[c] in right half

    Node(): best(0), mx(0) {}
};

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

// Merge two nodes a=[l..m], b=[m+1..r] into res=[l..r]
Node merge(const Node &a, const Node &b) {
    int nl = (int)a.L.size() + (int)a.R.size() + 1; // not actually used
    Node res;
    res.mx = max(a.mx, b.mx);
    // 1) best entirely in one side
    res.best = max(a.best, b.best);

    // Prepare L for res: pairs entirely in left child or crossing
    int lenL = a.L.size() + 1;  // interval length of left child
    int lenR = b.R.size() + 1;  // length of right child
    int len = lenL + lenR;
    res.L.assign(len, LLONG_MIN);
    res.R.assign(len, LLONG_MIN);

    // 2) copy old L pairs from a
    for (int d = 1; d < (int)a.L.size(); d++)
        res.L[d] = max(res.L[d], a.L[d]);

    // 3) pairs entirely in b but re‐indexed to global
    for (int d = 1; d < (int)b.L.size(); d++)
        res.L[d + lenL] = max(res.L[d + lenL], b.L[d]);

    // 4) similarly for R
    for (int d = 1; d < (int)b.R.size(); d++)
        res.R[d] = max(res.R[d], b.R[d]);
    for (int d = 1; d < (int)a.R.size(); d++)
        res.R[d + lenR] = max(res.R[d + lenR], a.R[d]);

    // 5) now handle triples that cross—i.e. a pair from left child of offset d1,
    //    a single from the boundary, and a pair from right child of offset d2,
    //    subject to d1 <= d2.
    // Actually it suffices to scan all d where both res.L[d], res.R[d] are valid:
    for (int d = 1; d < len; d++) {
        if (res.L[d] > LLONG_MIN/2 && res.R[d] > LLONG_MIN/2) {
            res.best = max(res.best, res.L[d] + res.R[d] - /*A[b] counted twice*/ 0);
        }
    }

    // Finally, any triple using two from one side and one singleton from the other?
    // Actually those are already included in a.best or b.best, or in the scan above.

    return res;
}

void build(int idx, int l, int r) {
    if (l == r) {
        seg[idx].best = 0;       // no triple in a single point
        seg[idx].mx   = A[l];
        seg[idx].L = seg[idx].R = vector<ll>(2, LLONG_MIN);
        // no valid d=1 pair in a single point
        return;
    }
    int m = (l + r) >> 1;
    build(idx<<1, l, m);
    build(idx<<1|1, m+1, r);
    seg[idx] = merge(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);
    return merge(
        query(idx<<1,   l,   m, ql, qr),
        query(idx<<1|1, m+1, r, ql, qr)
    );
}

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

    int Q;
    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);
        cout << ans.best << "\n";
    }
    return 0;
}

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