Submission #538996

#	Time	Username	Problem	Language	Result	Execution time	Memory
538996		Monarchuwu	Triple Jump (JOI19_jumps)	C++17	100 / 100	830 ms	50508 KiB

jumps

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 5e5 + 5;
int n, q;
int a[N];

struct Query {
    int l, r, id;
    bool operator < (const Query &o) const { return l > o.l; }
} Q[N];

int st[N], top;
int cnt;
pii p[N << 1];
void init() {
    for (int i = 1; i <= n; ++i) {
        while (top && a[st[top]] < a[i]) --top;
        if (top) p[++cnt] = pii(st[top], i);
        st[++top] = i;
    }

    top = 0;
    for (int i = n; i; --i) {
        while (top && a[st[top]] < a[i]) --top;
        if (top) p[++cnt] = pii(i, st[top]);
        st[++top] = i;
    }
}

int seg[1 << 20], laz[1 << 20], ma1[1 << 20], ma2[1 << 20];
void build(int u, int l, int r) {
    if (l == r) seg[u] = ma1[u] = a[l];
    else {
        int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
        build(u1, l, m);
        build(u2, m + 1, r);
        seg[u] = ma1[u] = max(ma1[u1], ma1[u2]);
    }
}
void update(int u, int l, int r, int a, int b, int v) {
    if (a <= l && r <= b) {
        if (ma2[u] < v) {
            ma2[u] = laz[u] = v;
            seg[u] = max(seg[u], v + ma1[u]);
        }
        return;
    }
    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    if (laz[u]) {
        if (laz[u] > ma2[u1]) {
            ma2[u1] = laz[u1] = laz[u];
            seg[u1] = max(seg[u1], laz[u] + ma1[u1]);
        }
        if (laz[u] > ma2[u2]) {
            ma2[u2] = laz[u2] = laz[u];
            seg[u2] = max(seg[u2], laz[u] + ma1[u2]);
        }
        laz[u] = 0;
    }

    if (a <= m) update(u1, l, m, a, b, v);
    if (m < b) update(u2, m + 1, r, a, b, v);
    seg[u] = max(seg[u1], seg[u2]);
}
void update(int l, int r, int v) {
    if (l <= r) update(1, 1, n, l, r, v);
}
int get(int u, int l, int r, int a, int b) {
    if (a <= l && r <= b) return seg[u];
    if (b < l || r < a) return 0;

    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    if (laz[u]) {
        if (laz[u] > ma2[u1]) {
            ma2[u1] = laz[u1] = laz[u];
            seg[u1] = max(seg[u1], laz[u] + ma1[u1]);
        }
        if (laz[u] > ma2[u2]) {
            ma2[u2] = laz[u2] = laz[u];
            seg[u2] = max(seg[u2], laz[u] + ma1[u2]);
        }
        laz[u] = 0;
    }
    return max(get(u1, l, m, a, b), get(u2, m + 1, r, a, b));
}

int ans[N];
void solve() {
    init();
    sort(Q + 1, Q + q + 1);
    sort(p + 1, p + cnt + 1, [](const pii &a, const pii &b) { return a.ff > b.ff; });

    build(1, 1, n);
    for (int i = 1, j = 1; i <= q; ++i) {
        while (j <= cnt && p[j].ff >= Q[i].l) {
            update(p[j].ss * 2 - p[j].ff, n, a[p[j].ff] + a[p[j].ss]);
            ++j;
        }
        ans[Q[i].id] = get(1, 1, n, Q[i].l, Q[i].r);
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    cin >> q;
    for (int i = 1; i <= q; ++i)
        cin >> Q[i].l >> Q[i].r, Q[i].id = i;

    solve();
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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