Submission #397727

#	Time	Username	Problem	Language	Result	Execution time	Memory
397727		timmyfeng	Triple Jump (JOI19_jumps)	C++17	100 / 100	2115 ms	147880 KiB

jumps

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

const int N = 500000;

struct segtree {
    segtree *left, *right;
    int first, second, maxi;

    void apply(int x) {
        first = max(first, x);
        maxi = max(maxi, first + second);
    }

    void push() {
        left->apply(first);
        right->apply(first);
    }

    void pull() {
        second = max(left->second, right->second);
        maxi = max({maxi, left->maxi, right->maxi});
    }

    segtree(int l, int r, int *a) {
        first = maxi = INT_MIN;
        if (l == r) {
            second = a[l];
            maxi = first + second;
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m, a);
            right = new segtree(m + 1, r, a);
            pull();
        }
    }

    void update(int a, int b, int x, int l, int r) {
        if (a > b || b < l || r < a) {
            return;
        } else if (a <= l && r <= b) {
            apply(x);
        } else {
            push();
            int m = (l + r) / 2;
            left->update(a, b, x, l, m);
            right->update(a, b, x, m + 1, r);
            pull(); 
        }
    }

    int query(int a, int b, int l, int r) {
        if (b < l || r < a) {
            return INT_MIN;
        } else if (a <= l && r <= b) {
            return maxi;
        } else {
            push();
            int m = (l + r) / 2;
            return max(left->query(a, b, l, m), right->query(a, b, m + 1, r));
        }
    }
};

vector<array<int, 2>> queries[N];
int a[N], order[N], ans[N];
vector<int> pairs[N];

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

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    iota(order, order + n, 0);
    stable_sort(order, order + n, [&](int i, int j) {
        return a[i] > a[j];
    });

    set<int> indices;
    for (int i = 0; i < n; ++i) {
        auto it = indices.lower_bound(order[i]);

        if (it != indices.end()) {
            pairs[order[i]].push_back(*it);
        }

        if (it != indices.begin()) {
            pairs[*--it].push_back(order[i]);
        }

        indices.insert(order[i]);
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[l - 1].push_back({r - 1, i});
    }

    segtree *maxi = new segtree(0, n - 1, a);

    for (int i = n - 1; i >= 0; --i) {
        for (auto j : pairs[i]) {
            maxi->update(2 * j - i, n - 1, a[i] + a[j], 0, n - 1);
        }

        for (auto [j, k] : queries[i]) {
            ans[k] = maxi->query(i, j, 0, n - 1);
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

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