Submission #1256048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256048		namhh	Triple Jump (JOI19_jumps)	C++20	100 / 100	775 ms	48948 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e5+5;
int n,q,a[N],lazy[4*N],st1[4*N],st2[4*N],ans[N];
stack<int>st;
vector<pii>adj[N];
void build(int id, int l, int r){
	if(l == r){
		st1[id] = a[l];
		return;
	}
	int mid = (l+r)/2;
	build(2*id,l,mid);
	build(2*id+1,mid+1,r);
	st1[id] = max(st1[2*id],st1[2*id+1]);
}
void down(int id){
	if(lazy[id] != 0){
		st2[2*id] = max(st2[2*id],lazy[id]+st1[2*id]);
		st2[2*id+1] = max(st2[2*id+1],lazy[id]+st1[2*id+1]);
		lazy[2*id] = max(lazy[2*id],lazy[id]);
		lazy[2*id+1] = max(lazy[2*id+1],lazy[id]);
		lazy[id] = 0;
	}
}
void update(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st2[id] = max(st2[id],val+st1[id]);
		lazy[id] = max(lazy[id],val);
		return;
	}
	if(l != r) down(id);
	int mid = (l+r)/2;
	update(2*id,l,mid,u,v,val);
	update(2*id+1,mid+1,r,u,v,val);
	st2[id] = max(st2[2*id],st2[2*id+1]);
}
int get(int id, int l, int r, int u, int v){
	if(l != r) down(id);
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return st2[id];
	int mid = (l+r)/2;
	return max(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	build(1,1,n);
	cin >> q;
	for(int i = 1; i <= q; i++){
		int l,r;
		cin >> l >> r;
		adj[l].push_back({r,i});
	}
	for(int i = n; i >= 1; i--){
		while(!st.empty() && a[st.top()] < a[i]){
			int x = 2*st.top()-i;
			update(1,1,n,x,n,a[i]+a[st.top()]);
			st.pop();
		}
		if(!st.empty()){
			int x = 2*st.top()-i;
			update(1,1,n,x,n,a[i]+a[st.top()]);
		}
		st.push(i);
		for(auto[v,id]: adj[i]) ans[id] = get(1,1,n,i,v);
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

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