Submission #417967

#	Time	Username	Problem	Language	Result	Execution time	Memory
417967		nvmdava	3단 점프 (JOI19_jumps)	C++17	100 / 100	1358 ms	160800 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2000005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int SQ = 300;

int a[N];

int lz[N], con[N], ans[N];

void build(int id, int l, int r){
    if(l == r){
        con[id] = ans[id] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(id << 1, l, m);
    build(id << 1 | 1, m + 1, r);

    con[id] = ans[id] = max(con[id << 1], con[id << 1 | 1]);
}

void reset(int id, int l, int r){
    ans[id] = max(ans[id], con[id] + lz[id]);
}

void update(int id, int l, int r, int L, int R, int x){
    lz[id] = max(lz[id], lz[id >> 1]);
    ans[id] = max(ans[id], con[id] + lz[id]);
    if(r < L || R < l) return;
    if(L <= l && r <= R){
        lz[id] = max(lz[id], x);
        ans[id] = max(ans[id], con[id] + lz[id]);
        return;
    }
    int m = (l + r) >> 1;
    update(id << 1, l, m, L, R, x);
    update(id << 1 | 1, m + 1, r, L, R, x);
    ans[id] = max({ans[id], ans[id << 1], ans[id << 1 | 1]});
}

int query(int id, int l, int r, int L, int R){
    lz[id] = max(lz[id], lz[id >> 1]);
    ans[id] = max(ans[id], con[id] + lz[id]);
    if(r < L || R < l)
        return 0;
    if(L <= l && r <= R)
        return ans[id];
    int m = (l + r) >> 1;
    return max(query(id << 1, l, m, L, R), query(id << 1 | 1, m + 1, r, L, R));
}

vector<pair<int, int> > upd[N], que[N];
int res[N];

vector<int> tmp;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i = 1; i <= n; ++i)
        cin>>a[i];

    build(1, 1, n);

    for(int i = 1; i <= n; ++i){
        while(!tmp.empty() && a[tmp.back()] < a[i]){
            upd[tmp.back()].push_back({i * 2 - tmp.back(), a[i] + a[tmp.back()]});
            tmp.pop_back();
        }
        if(!tmp.empty())
            upd[tmp.back()].push_back({i * 2 - tmp.back(), a[i] + a[tmp.back()]});
        tmp.push_back(i);
    }
    
    int q;
    cin>>q;
    for(int l, r, i = 1; i <= q; ++i){
        cin>>l>>r;
        que[l].push_back({r, i});
    }

    for(int i = n; i >= 1; --i){
        for(auto& [pos, val] : upd[i])
            update(1, 1, n, pos, n, val);
        for(auto& [r, v] : que[i])
            res[v] = query(1, 1, n, i + 2, r);
    }

    for(int i = 1; i <= q; ++i)
        cout<<res[i]<<'\n';
}

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