Submission #1264578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264578		nguyenphucanhkhoi	Triple Jump (JOI19_jumps)	C++20	27 / 100	123 ms	16708 KiB

jumps

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

#define ll long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
#define hash vector<int>
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; i++)
#define REV(i, n) for (int i = (n); i >= 1; i--)
#define FOR(i, k, n) for (int i = (k), _n = (n); i <= _n; i++)
#define FOV(i, k, n) for (int i = (n), _n = (k); i >= _n; i--)
#define MASK(k) (1 << (k))
#define BIT(i, n) (((n) >> ((i) - 1)) & 1)
#define OFF(i, n) ((n) & ~MASK((i) - 1))
#define ON(i, n) ((n) | MASK((i) - 1))
#define NUM_BIT(n) (__builtin_popcount(n))

const int MAXN = 1e6 + 26;
int n, m, k, x, y, a[MAXN], ans[MAXN];
pii c[MAXN];
ll mx[4 * MAXN], pr[4 * MAXN], lazy[4 * MAXN];

void build(int k, int l, int r) {
    lazy[k] = -1e18;
    if (l == r) {
        mx[k] = -1e18;
        pr[k] = a[r];
        return;
    }
    int m = (l + r) >> 1;
    build(k << 1, l, m);
    build(k << 1 | 1, m + 1, r);
    mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
    pr[k] = max(pr[k << 1], pr[k << 1 | 1]);
}

void fix(int k, int l, int r) {
    if (lazy[k] == -1e18) return;
    mx[k] = max(mx[k], pr[k] + lazy[k]);
    if (l != r) {
        lazy[k << 1] = max(lazy[k << 1], lazy[k]);
        lazy[k << 1 | 1] = max(lazy[k << 1 | 1], lazy[k]);
    }
    lazy[k] = -1e18;
}

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

ll get(int k, int l, int r, int u, int v) {
    fix(k, l, r);
    if (l > v || r < u) return -1e18;
    if (l >= u && r <= v) return mx[k];
    int m = (l + r) >> 1;
    return max(get(k << 1, l, m, u, v), get(k << 1 | 1, m + 1, r, u, v));
}

struct query {
    int l, r, id;
} b[MAXN];

void find_pairs() {
    stack<int> st;
    REP(i, n) {
        while (!st.empty() && a[st.top()] <= a[i]) {
            c[++k] = {st.top(), i};
            st.pop();
        }
        if (!st.empty()) c[++k] = {st.top(), i};;
        st.push(i);
    }
    sort(c + 1, c + k + 1, greater<pii>());
}

bool cmp(query i1, query i2) {
    return i1.l < i2.l;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    REP(i, n) cin >> a[i];
    cin >> m;
    REP(i, m) cin >> x >> y, b[i] = {x, y, i};
    find_pairs();
    build(1, 1, n);
    sort(b + 1, b + m + 1, cmp);
    int j = 1;
    REP(i, m) {
        int l = b[i].l, r = b[i].r;
        while (c[j].fi >= l && j <= k) {
            int x = c[j].fi, y = c[j].se;
            int p = 2 * y - x;
            if (p <= n) update(1, 1, n, p, n, a[x] + a[y]);
            j++;
        }
        int id = b[i].id;
        ans[id] = get(1, 1, n, l, r);
    }
    REP(i, m) cout << ans[i] << endl;
    return 0;
}

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