Submission #1117913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117913		XRomanticCatX	Triple Jump (JOI19_jumps)	C++17	100 / 100	1637 ms	139252 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define pii pair<int , int>
#define f first
#define s second

const int MAXN = 1e6 + 5;

const int MOD = (119 >> 23) ^ 1;

const int INF = 1e10;

int p = 1;

struct segment{
	int val[MAXN * 2];
	int seg[MAXN * 2];
	int lazy[MAXN * 2];
	segment(){
		for(int i = 1 ; i < MAXN * 2 ; i++){
			val[i] = 0;
			seg[i] = 0;
			lazy[i] = 0;
		}
	}
	void build(){
		for(int i = p - 1 ; i >= 1 ; i--){
			val[i] = max(val[i * 2] , val[i * 2 + 1]);
		}
	}
	int getmax(int v , int vl , int vr , int l , int r){
		if(vr < l || r < vl) return 0;
		if(vl >= l && vr <= r) return val[v];
		int mid = (vr + vl) >> 1;
		return max(getmax(v * 2 , vl , mid , l , r) , getmax(v * 2 + 1 , mid + 1 , vr , l , r));
	}
	void shift(int v){
		if(v >= p) return;
		lazy[v * 2] = max(lazy[v * 2] , lazy[v]);
		lazy[v * 2 + 1] = max(lazy[v * 2 + 1] , lazy[v]);
		seg[v * 2] = max(seg[v * 2] , lazy[v] + val[v * 2]);
		seg[v * 2 + 1] = max(seg[v * 2 + 1] , lazy[v] + val[v * 2 + 1]);
		lazy[v] = 0;
	}
	void update(int v , int vl , int vr , int l , int r , int x){
		if(vr < l || r < vl) return;
		if(vl >= l && vr <= r){
			lazy[v] = max(lazy[v] , x);
			seg[v] = max(seg[v] , x + val[v]);
			return;
		}
		shift(v);
		int mid = (vr + vl) >> 1;
		update(v * 2 , vl , mid , l , r , x);
		update(v * 2 + 1 , mid + 1 , vr , l , r , x);
		seg[v] = max(seg[v * 2] , seg[v * 2 + 1]); 
	}
	int getans(int v , int vl , int vr , int l , int r){
		if(vr < l || r < vl) return 0;
		if(vl >= l && vr <= r) return seg[v];
		shift(v);
		int mid = (vr + vl) >> 1;
		return max(getans(v * 2 , vl , mid , l , r) , getans(v * 2 + 1 , mid + 1 , vr , l , r));
	}
};

segment tree;

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0) ,cout.tie(0);
	int n;
	cin>>n;
	while(p < n) p *= 2;
	int a[n + 5];
	for(int i = 1 ; i <= n ; i++){
		cin>>a[i];
		tree.val[i + p] = a[i];
	}
	tree.build();
	int lef[n + 5];
	int rig[n + 5];
	stack <pii> st;
	st.push({INF , 0});
	for(int i = 1 ; i <= n ; i++){
		while(!st.empty() and a[i] > st.top().f){
			st.pop();
		}
		lef[i] = st.top().s;
		st.push({a[i] , i});
	}
	stack <pii> stt;
	stt.push({INF , n + 1});
	for(int i = n ; i >= 1 ; i--){
		while(!stt.empty() and a[i] > stt.top().f){
			stt.pop();
		}
		rig[i] = stt.top().s;
		stt.push({a[i] , i});
	}
	vector <int> update[n + 5];
	vector <pii> query[n + 5];
	for(int i = n ; i >= 1 ; i--){
		if(lef[i]) update[lef[i]].push_back(i);
		if(rig[i] <= n) update[i].push_back(rig[i]); 
	}	
	int q;
	cin>>q;
	int fq = q;
	while(q--){
		int l , r;
		cin>>l>>r;
		query[l].push_back({r , fq - q});
	}
	int ans[fq + 5];
	for(int i = n - 1 ; i >= 1 ; i--){
		for(auto u : update[i]){
			tree.update(1 , 0 , p - 1 , u + u - i , n , a[i] + a[u]);
		}
		for(auto u : query[i]){
			ans[u.s] = tree.getans(1 , 0 , p - 1 , i , u.f);
		}
	}
	for(int i = 1 ; i <= fq ; i++){
		cout<<ans[i]<<endl;
	}
}

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