Submission #333043

#	Time	Username	Problem	Language	Result	Execution time	Memory
333043		phathnv	Triple Jump (JOI19_jumps)	C++11	100 / 100	1351 ms	88060 KiB

jumps

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 5e5 + 2;
const int INF = 1e9;

struct segmentTree{
    int n, maxVal[N * 4], lazy[N * 4], maxA[N * 4];
    void build(int id, int l, int r, int a[N]){
        if (l == r){
            maxVal[id] = maxA[id] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, a);
        build(id << 1 | 1, mid + 1, r, a);
        maxVal[id] = max(maxVal[id << 1], maxVal[id << 1 | 1]);
        maxA[id] = max(maxA[id << 1], maxA[id << 1 | 1]);
    }
    void doLazy(int id, int l, int r){
        maxVal[id] = max(maxVal[id], lazy[id] + maxA[id]);
        if (l < r){
            lazy[id << 1] = max(lazy[id << 1], lazy[id]);
            lazy[id << 1 | 1] = max(lazy[id << 1 | 1], lazy[id]);
        }
    }
    void update(int id, int l, int r, int u, int v, int val){
        doLazy(id, l, r);
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            lazy[id] = max(lazy[id], val);
            doLazy(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        maxVal[id] = max(maxVal[id << 1], maxVal[id << 1 | 1]);
    }
    int getMax(int id, int l, int r, int u, int v){
        doLazy(id, l, r);
        if (v < l || r < u)
            return 0;
        if (u <= l && r <= v)
            return maxVal[id];
        int mid = (l + r) >> 1;
        return max(getMax(id << 1, l, mid, u, v), getMax(id << 1 | 1, mid + 1, r, u, v));
    }

    void init(int _n, int a[N]){
        assert(_n > 0);
        n = _n;
        build(1, 1, n, a);
    }
    void update(int l, int r, int val){
        assert(1 <= l && l <= r && r <= n);
        update(1, 1, n, l, r, val);
    }
    int getMax(int l, int r){
        assert(1 <= l && l <= r && r <= n);
        return getMax(1, 1, n, l, r);
    }
} ST;

int n, q, a[N], answer[N];
vector <int> imp[N];
vector <ii> query[N];

void readInput(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    for(int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        query[l].push_back(mp(r, i));
    }
}

void solve(){
    stack <int> st;
    a[n + 1] = INF;
    st.push(n + 1);
    for(int i = n; i >= 1; i--){
        while (a[i] > a[st.top()]){
            imp[i].push_back(st.top());
            st.pop();
        }
        if (st.top() != n + 1)
            imp[i].push_back(st.top());
        st.push(i);
    }

    ST.init(n, a);
    for(int l = n; l >= 1; l--){
        for(int r : imp[l]){
            int k = 2 * r - l;
            if (k <= n)
                ST.update(k, n, a[l] + a[r]);
        }
        for(ii qr : query[l]){
            int r = qr.X;
            int ind = qr.Y;
            answer[ind] = ST.getMax(l, r);
        }
    }
    for(int i = 1; i <= q; i++)
        cout << answer[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    readInput();
    solve();
    return 0;
}

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