Submission #1264564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264564		nguyenphucanhkhoi	Triple Jump (JOI19_jumps)	C++20	100 / 100	657 ms	53924 KiB

jumps

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

#define ll long long
const int MAXN = 1e6 + 26;
const ll INF = 1e18;

int n, m, a[MAXN];
ll ans[MAXN];
vector<pair<int, int>> candidates;
vector<tuple<int, int, int>> queries;

struct SegmentTree {
    ll tree[4 * MAXN], lazy[4 * MAXN];
    ll pr[4 * MAXN]; // max a[z] in segment

    void build(int k, int l, int r) {
        lazy[k] = -INF;
        if (l == r) {
            tree[k] = -INF;
            pr[k] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(2*k, l, m);
        build(2*k+1, m+1, r);
        tree[k] = max(tree[2*k], tree[2*k+1]);
        pr[k] = max(pr[2*k], pr[2*k+1]);
    }

    void push(int k, int l, int r) {
        if (lazy[k] != -INF) {
            tree[k] = max(tree[k], pr[k] + lazy[k]);
            if (l != r) {
                lazy[2*k] = max(lazy[2*k], lazy[k]);
                lazy[2*k+1] = max(lazy[2*k+1], lazy[k]);
            }
            lazy[k] = -INF;
        }
    }

    void update(int k, int l, int r, int u, int v, ll f) {
        push(k, l, r);
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            lazy[k] = f;
            push(k, l, r);
            return;
        }
        int m = (l + r) >> 1;
        update(2*k, l, m, u, v, f);
        update(2*k+1, m+1, r, u, v, f);
        tree[k] = max(tree[2*k], tree[2*k+1]);
    }

    ll query(int k, int l, int r, int u, int v) {
        push(k, l, r);
        if (l > v || r < u) return -INF;
        if (l >= u && r <= v) return tree[k];
        int m = (l + r) >> 1;
        return max(query(2*k, l, m, u, v), query(2*k+1, m+1, r, u, v));
    }
} seg;

void find_pairs() {
    stack<int> st;
    for (int j = 1; j <= n; j++) {
        while (!st.empty() && a[st.top()] < a[j]) {
            int i = st.top(); st.pop();
            candidates.push_back({i, j});
        }
        if (!st.empty()) {
            candidates.push_back({st.top(), j});
        }
        st.push(j);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; i++) {
        int l, r; cin >> l >> r;
        queries.emplace_back(l, r, i);
    }

    find_pairs();
    seg.build(1, 1, n);

    // Sort queries by l descending
    sort(queries.rbegin(), queries.rend());
    // Sort candidates by i descending
    sort(candidates.rbegin(), candidates.rend());

    int j = 0;
    for (auto [l, r, idx] : queries) {
        while (j < candidates.size() && candidates[j].first >= l) {
            int i = candidates[j].first, j_val = candidates[j].second;
            int z_min = 2 * j_val - i;
            if (z_min <= n) {
                seg.update(1, 1, n, z_min, n, a[i] + a[j_val]);
            }
            j++;
        }
        ans[idx] = seg.query(1, 1, n, l, r);
    }

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

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