Submission #833118

#	Time	Username	Problem	Language	Result	Execution time	Memory
833118		PurpleCrayon	Triple Jump (JOI19_jumps)	C++17	5 / 100	4043 ms	170060 KiB

jumps

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 5e5+10, INF = 1e9+10;
const int L = 100;

using ui = unsigned int;

// b - a <= c - b
// 2b <= a + c
// c >= 2b - a
// a >= 2b - c
// consider the O(log) biggest elements
// at least one of those must be in the optimal solution

int n, q, a[N];
ui ans[N];
int st[N][L];
vector<ar<int, 2>> qs[N];
ar<int, L> store[N];

int qry(int l, int r) {
    if (l > r) return -INF;
    int b = 31 - __builtin_clz(r - l + 1);
    return max(st[l][b], st[r - (1 << b) + 1][b]);
}

bool better(int x, int y) {
    return a[x] > a[y];
}

void add(ar<int, L>& x, int y) {
    for (int i = L-1; i >= 0; i--) {
        if (better(y, x[i])) {
            if (i < L-1) x[i+1] = x[i];
        } else {
            if (i < L-1) x[i+1] = y;
            return;
        }
    }
    x[0] = y;
}

ar<int, L> merge(const ar<int, L>& x, const ar<int, L>& y) {
    int p1 = 0, p2 = 0;
    ar<int, L> ans;
    for (int i = 0; i < L; i++) {
        if (p1 < L && (p2 == L || better(x[p1], y[p2]))) ans[i] = x[p1++];
        else ans[i] = y[p2++];
    }
    return ans;
}

ui calc(int x, int y, int l, int r) {
    if (x > y) swap(x, y);

    int ans = 0;
    ans = max(ans, qry(x + 1, (x + y) / 2));
    ans = max(ans, qry(2 * y - x, r));
    ans = max(ans, qry(max(l, 2 * x - y), x - 1));
    return ui(ans) + a[x] + a[y];
}

void rec(int l, int r) {
    if (r - l <= 1) return;
    int m = (l + r) / 2;

    store[m+1].fill(n);
    for (int i = m; i >= l; i--) {
        copy(store[i+1].begin(), store[i+1].end(), store[i].begin());
        add(store[i], i);
    }

    ar<int, L> cur; cur.fill(n);
    for (int i = m+1; i <= r; i++) {
        add(cur, i);
        for (auto [ql, id] : qs[i]) {
            if (ql < l || ql > m) continue;
            ar<int, L> use = merge(cur, store[ql]);
            // for (int x : use) cerr << x << ' ';
            // cerr << endl;
            for (int x = 0; x < L; x++) if (use[x] < n) {
                for (int y = 0; y < x; y++) {
                    ans[id] = max(ans[id], calc(use[x], use[y], ql, i));
                }
            }
        }
    }


    rec(l, m), rec(m+1, r);
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        st[i][0] = a[i];
    }
    a[n] = -1;

    for (int k = 1; n >> k; k++) {
        for (int i = 0; i + (1 << k) <= n; i++) {
            st[i][k] = max(st[i][k-1], st[i + (1 << (k-1))][k-1]);
        }
    }

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

    rec(0, n-1);

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

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    solve();
}

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