Submission #683032

#	Time	Username	Problem	Language	Result	Execution time	Memory
683032		tht2005	Triple Jump (JOI19_jumps)	C++17	100 / 100	1047 ms	99896 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define M 524288
int st[M << 1], A[M << 1], B[M << 1], C[M << 1], lz[M << 1];
//                         MIN        MAX

void push(int x, int l, int r) {
    if(lz[x] > 0) {
        st[x] = A[x] + lz[x];
        B[x] = C[x] = lz[x];
        if(l != r) {
            lz[x << 1] = lz[x << 1 | 1] = lz[x];
        }
        lz[x] = 0;
    }
}
void update(int x, int l, int r, int ql, int qr, int d) {
    push(x, l, r);
    if(r < ql || qr < l || B[x] >= d) {
        return;
    }
    if(ql <= l && r <= qr && C[x] <= d) {
        lz[x] = d;
        push(x, l, r);
    }
    else {
        int m = (l + r) >> 1;
        update(x << 1, l, m, ql, qr, d);
        update(x << 1 | 1, m + 1, r, ql, qr, d);
        st[x] = max(st[x << 1], st[x << 1 | 1]);
        B[x] = min(B[x << 1], B[x << 1 | 1]);
        C[x] = max(C[x << 1], C[x << 1 | 1]);
    }
}
int query(int x, int l, int r, int ql, int qr) {
    push(x, l, r);
    if(r < ql || qr < l) {
        return 0;
    }
    if(ql <= l && r <= qr) {
        return st[x];
    }
    int m = (l + r) >> 1;
    return max(query(x << 1, l, m, ql, qr), query(x << 1 | 1, m + 1, r, ql, qr));
}

#define N 500005
int a[N], L[N], R[N], res[N];
vector<int> pot[N];
vector<pair<int, int>> queries[N];

void build(int x, int l, int r) {
    st[x] = B[x] = C[x] = 0;
    if(l == r) {
        A[x] = a[l];
    }
    else {
        int m = (l + r) >> 1;
        build(x << 1, l, m);
        build(x << 1 | 1, m + 1, r);
        A[x] = max(A[x << 1], A[x << 1 | 1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for(int i = 1, j; i <= n; ++i) {
        j = i - 1;
        while(j > 0 && a[i] > a[j]) {
            j = L[j];
        }
        L[i] = j;
    }
    for(int i = n, j; i > 0; --i) {
        j = i + 1;
        while(j <= n && a[i] > a[j]) {
            j = R[j];
        }
        R[i] = j;
    }
    for(int i = 1; i <= n; ++i) {
        if(L[i] > 0) {
            pot[L[i]].push_back(i);
        }
        if(R[i] <= n) {
            pot[i].push_back(R[i]);
        }
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[l].emplace_back(i, r);
    }
    build(1, 1, n);
    for(int i = n; i > 0; --i) {
        sort(pot[i].begin(), pot[i].end());
        pot[i].erase(unique(pot[i].begin(), pot[i].end()), pot[i].end());
        for(int j : pot[i]) {
            int k_min = j + j - i;
            if(k_min <= n) {
                update(1, 1, n, k_min, n, a[i] + a[j]);
            }
        }
        for(const auto& [j, r] : queries[i]) {
            res[j] = query(1, 1, n, i, r);
        }
    }
    for(int i = 1; i <= q; ++i) {
        cout << res[i] << '\n';
    }
    return 0;
}

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