Submission #1209166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209166		Boomyday	Triple Jump (JOI19_jumps)	C++20	27 / 100	218 ms	47088 KiB

jumps

//
// Created by adavy on 5/28/2025.
//
#include <bits/stdc++.h>
using namespace std;


using ll = long long;
int ssz = 524288;
ll INF = 1e18;


int n;
vector<ll> nums;
vector<ll> nummax(ssz*2, -INF);
vector<ll> seg(ssz*2, -INF);
vector<ll> lz(ssz*2, -INF);

void pushdown(int rt, int tl, int tr){
    seg[rt] = max(seg[rt], lz[rt] + nummax[rt]);
    if (tl != tr) {
        lz[2 * rt] = max(lz[2 * rt], lz[rt]);
        lz[2 * rt + 1] = max(lz[2 * rt + 1], lz[rt]);
    }
    lz[rt] = -INF;
}

ll query(int l, int r, int rt, int tl, int tr){
    if (l > tr || r < tl) return -INF;
    pushdown(rt, tl, tr);
    if (l <= tl && tr <= r) return seg[rt];
    int tm = (tl + tr) / 2;
    return max(query(l, r, 2 * rt, tl, tm), query(l, r, 2 * rt + 1, tm + 1, tr));
}

void update(ll x, int l, int r, int rt, int tl, int tr){
    if (l > tr || r < tl) return;
    pushdown(rt, tl, tr);
    if (l <= tl && tr <= r) {
        lz[rt] = max(lz[rt], x);
        pushdown(rt, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    update(x, l, r, 2 * rt, tl, tm);
    update(x, l, r, 2 * rt + 1, tm + 1, tr);
    seg[rt] = max(seg[2 * rt], seg[2 * rt + 1]);
}

void set_nummax(){
    for(int i=0;i<n;++i) nummax[ssz + i] = nums[i];
    for (int i = ssz - 1; i > 0; --i) {
        nummax[i] = max(nummax[2 * i], nummax[2 * i + 1]);
    }

}

int main(){
    cin >> n;
    nums.resize(n);
    for(int i=0;i<n;++i){
        cin >> nums[i];
    }
    // first, find the good ranges
    // do this using a nextmax array
    vector<int> nextmax(n, n);
    stack<int> st;
    for(int i=n-1;i>=0;--i){
        while(!st.empty() && nums[st.top()] <= nums[i]) st.pop();
        if (!st.empty()) nextmax[i] = st.top();
        st.push(i);
    }

    vector<vector<pair<int,ll>>> good(n); // left, pivot, val
    for(int left = 0;left < n-1;++left){
        int right = left + 1;
        do {
            int pivot = 2*right - left;
            if (pivot >= n) break;
            good[left].push_back({pivot, nums[left] + nums[right]});
            if (nums[right] >= nums[left]) break;
            right = nextmax[right];
        } while (right < n);
    }
    // print all the good triples


    set_nummax();
    // add at LEFT from PIVOT to end with VAL
    // now load in the queries
    vector<vector<pair<int,int>>> quers(n); // left, right, id

    int q; cin >> q;
    vector<ll> ans(q, -INF); // answer for each query
    for(int i=0;i<q;++i){
        int l, r; cin >> l >> r; l--; r--;
        quers[l].push_back({r, i});
    }
    for(int l = n-1;l>=0;--l){
        // first, insert the necessary ranges
        for(auto& [pivot, val] : good[l]) {
            update(val, pivot, n-1, 1, 0, ssz-1);
        }
        // then, carry out the necessary queries
        for(auto& [r, ind]:quers[l]){
            ans[ind] = query(0, r, 1, 0, ssz-1);
        }
    }
    for(auto&x:ans) cout << x << endl;

}

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