Submission #893643

#	Time	Username	Problem	Language	Result	Execution time	Memory
893643		Alcabel	Triple Jump (JOI19_jumps)	C++17	100 / 100	860 ms	93260 KiB

jumps

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

const int maxn = 5e5, inf = 1e9;
vector<pair<int, int>> cands[maxn], queries[maxn];

struct SegTree {
    int n, N;
    vector<int> bestP, sum, lazy;
    SegTree() {}
    SegTree(int _n) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        bestP.resize(2 * N, -inf);
        sum.resize(2 * N, -inf);
        lazy.resize(2 * N, -inf);
    }
    void push(int v) {
        sum[v] = max(sum[v], bestP[v] + lazy[v]);
        if (v < N) {
            lazy[2 * v] = max(lazy[2 * v], lazy[v]);
            lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
        }
        lazy[v] = -inf;
    }
    void insertP(int v, int tl, int tr, int i, int x) {
        if (lazy[v] != -inf) {
            push(v);
        }
        if (tl > i || tr <= i) {
            return;
        }
        if (tl + 1 == tr) {
            bestP[v] = max(bestP[v], x);
            return;
        }
        int m = tl + (tr - tl) / 2;
        insertP(2 * v, tl, m, i, x);
        insertP(2 * v + 1, m, tr, i, x);
        bestP[v] = max(bestP[2 * v], bestP[2 * v + 1]);
    }
    void insertP(int i, int x) {
        insertP(1, 0, N, i, x);
    }
    void maxEq(int v, int tl, int tr, int l, int r, int x) {
        if (lazy[v] != -inf) {
            push(v);
        }
        if (tl >= r || tr <= l) {
            return;
        }
        if (l <= tl && tr <= r) {
            lazy[v] = x;
            push(v);
            return;
        }
        int m = tl + (tr - tl) / 2;
        maxEq(2 * v, tl, m, l, r, x);
        maxEq(2 * v + 1, m, tr, l, r, x);
        sum[v] = max(sum[2 * v], sum[2 * v + 1]);
    }
    void maxEq(int l, int r, int x) {
        maxEq(1, 0, N, l, r, x);
    }
    int getMax(int v, int tl, int tr, int l, int r) {
        if (lazy[v] != -inf) {
            push(v);
        }
        if (tl >= r || tr <= l) {
            return -inf;
        }
        if (l <= tl && tr <= r) {
            return sum[v];
        }
        int m = tl + (tr - tl) / 2;
        return max(getMax(2 * v, tl, m, l, r), getMax(2 * v + 1, m, tr, l, r));
    }
    int getMax(int l, int r) {
        return getMax(1, 0, N, l, r);
    }
    ~SegTree() {}
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> leftGreq(n, -1), rightGreq(n, n), stk;
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && a[stk.back()] < a[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            leftGreq[i] = stk.back();
        }
        stk.emplace_back(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && a[stk.back()] < a[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            rightGreq[i] = stk.back();
        }
        stk.emplace_back(i);
    }
    stk.clear();
    for (int i = 0; i < n; ++i) {
        if (rightGreq[i] != n && rightGreq[i] - i + rightGreq[i] < n) {
            cands[2 * rightGreq[i] - i].emplace_back(i, rightGreq[i]);
        }
    }
    for (int j = n - 1; j >= 0; --j) {
        if (leftGreq[j] != -1 && j - leftGreq[j] + j < n) {
            cands[2 * j - leftGreq[j]].emplace_back(leftGreq[j], j);
        }
    }
    int q;
    cin >> q;
    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        queries[r].emplace_back(l, i);
    }
    SegTree st(n);
    for (int r = 0; r < n; ++r) {
        while (!cands[r].empty()) {
            auto [i, j] = cands[r].back();
            cands[r].pop_back();
            st.insertP(i, a[i] + a[j]);
        }
        st.maxEq(0, r, a[r]);
        while (!queries[r].empty()) {
            auto [l, i] = queries[r].back();
            queries[r].pop_back();
            ans[i] = st.getMax(l, r);
        }
    }
    for (const int& x : ans) {
        cout << x << '\n';
    }
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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