제출 #1209196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209196		Boomyday	Triple Jump (JOI19_jumps)	C++20	100 / 100	1548 ms	108460 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){
    pushdown(rt, tl, tr);
    if (l > tr || r < tl) return -INF;

    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){
    pushdown(rt, tl, tr);
    if (l > tr || r < tl) return;

    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]);
    }

}

signed 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<pair<int,int>> lrvals(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});
        lrvals[i] = {l, r};
    }

    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);
        }
    }
    /*

    vector<ll> simple_ans(q, -INF);
    for(int qq=0;qq<q;++qq){
        int l = lrvals[qq].first, r = lrvals[qq].second;
        for(int a=l;a<=r;++a){
            for (int b = a+1;b<=r;++b){
                for(int c = b+1; c <= r; ++ c){
                    if (c-b >= b-a) simple_ans[qq] = max(simple_ans[qq], nums[a] + nums[b] + nums[c]);
                }
            }
        }
    }*/

    for (int i=0;i<q;++i){
        cout << ans[i] <<endl;

    }

}

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