Submission #1122626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122626		Pacybwoah	Triple Jump (JOI19_jumps)	C++20	100 / 100	856 ms	90492 KiB

jumps

#include<iostream>
#include<vector>
using namespace std;
const int mininf = -1e9;
struct node{
    int ma, mb, sum;
    node(int _ma, int _mb, int _sum){
        ma = _ma, mb = _mb, sum = _sum;
    }
};
vector<node> seg;
inline node pull(node a, node b){
    return node(max(a.ma, b.ma), max(a.mb, b.mb), max(max(a.sum, b.sum), a.ma + b.mb));
}
void build(int l, int r, int ind, vector<int>& vec){
    if(l == r){
        seg[ind].mb = vec[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ind * 2, vec);
    build(mid + 1, r, ind * 2 + 1, vec);
    seg[ind] = pull(seg[ind * 2], seg[ind * 2 + 1]);
}
void modify(int l, int r, int pos, int num, int ind){
    if(l == r){
        seg[ind].ma = max(seg[ind].ma, num);
        seg[ind].sum = max(seg[ind].sum, seg[ind].ma + seg[ind].mb);
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) modify(l, mid, pos, num, ind * 2);
    else modify(mid + 1, r, pos, num, ind * 2 + 1);
    seg[ind] = pull(seg[ind * 2], seg[ind * 2 + 1]);
}
node query(int l, int r, int start, int end, int ind){
    if(r < start || end < l) return node(mininf, mininf, mininf);
    else if(start <= l && r <= end) return seg[ind];
    int mid = (l + r) >> 1;
    return pull(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> vec(n + 1);
    seg.resize(4 * n + 4, node(mininf, mininf, mininf));
    for(int i = 1; i <= n; i++) cin >> vec[i];
    build(1, n, 1, vec);
    vector<vector<pair<int, int>>> sweep(n + 1), rngs(n + 1);
    vector<int> st;
    for(int i = 1; i <= n; i++){
        while(!st.empty() && vec[st.back()] < vec[i]){
            rngs[st.back()].emplace_back(i, vec[st.back()] + vec[i]);
            st.pop_back();
        }
        if(!st.empty()){
            rngs[st.back()].emplace_back(i, vec[st.back()] + vec[i]);
        }
        st.push_back(i);
    }
    int q;
    cin >> q;
    vector<int> ans(q);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        sweep[l].emplace_back(r, i);
    }
    for(int i = n; i > 0; i--){
        for(auto &[b, val]: rngs[i]){
            //cout << i << " " << b << "\n";
            if(2 * b - i <= n) modify(1, n, 2 * b - i, val, 1);
        }
        for(auto &[r, id]: sweep[i]){
            ans[id] = query(1, n, i, r, 1).sum;
        }
    }
    for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

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