Submission #142540

#	Time	Username	Problem	Language	Result	Execution time	Memory
142540		imeimi2000	Triple Jump (JOI19_jumps)	C++17	100 / 100	1289 ms	71860 KiB

jumps

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;
typedef pair<int, int> pii;

int n, q;
int A[500001];
pair<pii, int> Q[500000];
int ans[500000];
int L[500002];
int R[500002];
vector<int> P[500001];

const int inf = 1e9;

struct node {
    int L, R, LR;
    node() : L(-inf), R(-inf), LR(-inf) {}
    node operator+(const node &p) const {
        node ret = node();
        ret.L = max(L, p.L);
        ret.R = max(R, p.R);
        ret.LR = max({ LR, p.LR, L + p.R });
        return ret;
    }
} seg[1 << 20];

void init(int i, int s, int e) {
    if (s == e) {
        seg[i].R = A[s];
        seg[i].LR = seg[i].L + seg[i].R;
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

void update(int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[i].L = max(seg[i].L, v);
        seg[i].LR = seg[i].L + seg[i].R;
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i << 1, s, m, x, v);
    else update(i << 1 | 1, m + 1, e, x, v);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

node query(int i, int s, int e, int x) {
    if (x < s) return node();
    if (e <= x) return seg[i];
    int m = (s + e) / 2;
    return query(i << 1, s, m, x) + query(i << 1 | 1, m + 1, e, x);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<pii> B;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
        B.emplace_back(A[i], i);
    }
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> Q[i].first.first >> Q[i].first.second;
        Q[i].second = i;
    }
    sort(Q, Q + q);
    sort(B.begin(), B.end());
    for (pii it : B) {
        int i = it.second;
        int l = i, r = i;
        if (L[i - 1] != 0) l = L[i - 1];
        if (R[i + 1] != 0) r = R[i + 1];
        L[l] = L[r] = l;
        R[l] = R[r] = r;
        if (l > 1) P[l - 1].push_back(i);
        if (r < n) P[i].push_back(r + 1);
    }
    init(1, 1, n);
    for (int i = q, j = n + 1; i--; ) {
        int l, r;
        tie(l, r) = Q[i].first;
        while (j > l) {
            for (int k : P[--j]) {
                int x = k + k - j;
                if (x > n) continue;
                int v = A[j] + A[k];
                update(1, 1, n, x, v);
            }
        }
        ans[Q[i].second] = query(1, 1, n, r).LR;
    }
    for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
    return 0;
}

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