Submission #944994

#	Time	Username	Problem	Language	Result	Execution time	Memory
944994		itslq	Triple Jump (JOI19_jumps)	C++17	5 / 100	4037 ms	19932 KiB

jumps

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

vector<int> A;

struct node {
    int l, r, m, v;
    node *lc, *rc;

    node(int _l, int _r): l(_l), r(_r) {
        m = (l + r) >> 1;
        if (l == r) {
            v = A[l];
        } else {
            lc = new node(l, m);
            rc = new node(m + 1, r);

            v = max(lc -> v, rc -> v);
        }
    }

    int query(int _l, int _r) {
        if (l == _l && r == _r) {
            return v;
        } else if (_r <= m) {
            return lc -> query(_l, _r);
        } else if (_l > m) {
            return rc -> query(_l, _r);
        } else {
            return max(lc -> query(_l, m), rc -> query(m + 1, _r));
        }
    }
} *root;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, Q, L, R, S;
    cin >> N;

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

    root = new node(1, N);

    cin >> Q;
    while (Q--) {
        S = 0;
        cin >> L >> R;
        for (int l = L; l + 2 <= R; l++) {
            for (int r = l + 2; r <= R; r++) {
                S = max(S, A[l] + A[r] + root -> query(l + 1, (l + r) >> 1));
            }
        }
        cout << S << '\n';
    }

    return 0;
}

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