Submission #1162307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162307		giaminh2211	Triple Jump (JOI19_jumps)	C++20	100 / 100	708 ms	113924 KiB

jumps

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

const int N=6e5+13;
int n, q;
ll a[N];

struct Segtree{
    ll st[N << 2];
	ll vmax[N << 2];
    ll lazy[N << 2];

	void fix(int id, int l, int r){
		if(!lazy[id]) return;
		st[id]=max(st[id], lazy[id]+vmax[id]);
		lazy[id << 1]=max(lazy[id << 1], lazy[id]);
		lazy[id << 1 | 1]=max(lazy[id << 1 | 1], lazy[id]);
		lazy[id]=0;
	}

	void build(int id, int l, int r){
		if(l==r){
			vmax[id]=a[l];
			return;
		}
		int mid=l+r >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid+1, r);
		vmax[id]=max(vmax[id << 1], vmax[id << 1 | 1]);
	}

    void update(int id, int l, int r, int u, int v, ll val){
    	fix(id, l, r);
        if(l > v || r < u) return;
        if(u<=l && r<=v){
            lazy[id]=max(lazy[id], val);
            fix(id, l, r);
            return;
        }
        int mid=l+r >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid+1, r, u, v, val);
        st[id]=max(st[id << 1], st[id << 1 | 1]);
    }

    ll get(int id, int l, int r, int u, int v){
    	fix(id, l, r);
        if(l > v || r < u) return -1e9;
        if(u<=l && r<=v) return st[id];
        int mid=l+r >> 1;
        int get1=get(id << 1, l, mid, u, v);
        int get2=get(id << 1 | 1, mid+1, r, u, v);
        return max(get1, get2);
    }

    void update(int u, int v){
        update(1, 1, n, u, n, v);
    }

    int get(int u, int v){
        return get(1, 1, n, u, v);
    }
} st;

stack<int> s;
vector<int> nxt[N];
vector<int> qr[N];
ll l[N], r[N];
ll res[N];

void scan(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    st.build(1, 1, n);
    for(int i=n; i>=1; i--){
        while(!s.empty() && a[s.top()] <= a[i]){
            nxt[i].push_back(s.top());
            s.pop();
        }
        if(s.size()) nxt[i].push_back(s.top());
        s.push(i);
    }
    cin >> q;
    for(int i=1; i<=q; i++){
        cin >> l[i] >> r[i];
        qr[l[i]].push_back(i);
    }
}

void solve(){
    for(int i=n; i>=1; i--){
        for(int j: nxt[i]){
            if(2*j-i<=n){
            	//cout << "? " << i << ' ' << j << ' ' << 2*j-i << ' ' << a[i]+a[j] << '\n';
                st.update(2*j-i, a[i]+a[j]);
            }
        }
        for(int id: qr[i]){
            res[id]=st.get(i, r[id]);
        }
    }
    for(int i=1; i<=q; i++){
        cout << res[i] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

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