Submission #1159116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159116		dosts	Triple Jump (JOI19_jumps)	C++20	100 / 100	844 ms	134196 KiB

jumps

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 2e16,N = 1e6+1,MOD =  998244353;

struct Query {
    int r,id;
};



struct ST {
    vi t,mx,lz,ans;

    void build(int node,int l,int r,const vi& a) {
        if (l == r) {
            t[node] = a[l];
            return;
        }
        int m = (l+r) >> 1;
        build(2*node,l,m,a),build(2*node+1,m+1,r,a);
        t[node] = max(t[2*node],t[2*node+1]);
    }
    ST(int nn,const vi& a) {
        t.resize(4*nn+1);
        ans.resize(4*nn+1);
        mx.assign(4*nn+1,-inf);
        lz.assign(4*nn+1,-inf);
        build(1,1,nn,a);
    }
    void push(int node,bool leaf) {
        mx[node] = max(mx[node],lz[node]);
        ans[node] = max(ans[node],t[node]+mx[node]);
        if (!leaf) {
            lz[2*node] = max(lz[2*node],lz[node]);
            lz[2*node+1] = max(lz[2*node+1],lz[node]);
        }
        lz[node] = -inf;
    }

    void update(int node,int l,int r,int L,int R,int v) {
        push(node,l==r);
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            lz[node] = max(lz[node],v);
            push(node,l==r);
            return;
        }
        int m = (l+r) >> 1;
        update(2*node,l,m,L,R,v);
        update(2*node+1,m+1,r,L,R,v);
        ans[node] = max(ans[2*node],ans[2*node+1]);
    }

    int query(int node,int l,int r,int L,int R) {
        push(node,l==r);
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return ans[node];
        int m = (l+r) >> 1;
        return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }
};
void solve() {
    int n;
    cin >> n;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    vi ps[n+1];
    stack<int> stk;
    for (int i = n;i>=1;i--) {
        while (!stk.empty() && a[stk.top()] <= a[i]) {
            ps[i].push_back(stk.top());
            stk.pop();
        }
        if (!stk.empty()) ps[i].push_back(stk.top());
        stk.push(i);
    }
    int q;
    cin >> q;
    vector<Query> qs[n+1];
    vi ans(q+1);
    for (int i=1;i<=q;i++) {
        int l,r;
        cin >> l >> r;
        qs[l].push_back({r,i});
    }
    ST st(n,a);
    for (int i = n;i>=1;i--) {
        for (auto it : ps[i]) {
            int p = 2*it-i;
            st.update(1,1,n,p,n,a[i]+a[it]);
        }
        for (auto it : qs[i]) {
            ans[it.id] = st.query(1,1,n,i,it.r);
        }
    }
    for (int i=1;i<=q;i++) cout << ans[i] << '\n';
}



int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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