Submission #1255917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255917		mngoc._.	Triple Jump (JOI19_jumps)	C++20	100 / 100	842 ms	65732 KiB

jumps

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int , int>
const int N = 5e5 + 5;
pii st[4 * N];
int stadd[4 * N];
int a[N];

int res[N];
vector<pii> queries[N];
int n , q;

bool cmp(const pii& x, const pii& y){
	return x.second < y.second;
}
void build(int idx , int l , int r){
	if(l == r){
		st[idx].first = a[l];
		st[idx].second = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(2 * idx , l , mid);
	build(2 * idx + 1 , mid + 1 , r);
	st[idx].first = max(st[2 * idx].first , st[2 * idx + 1].first);
	st[idx].second = st[idx].first;
	
}

void update(int idx , int l , int r , int u , int v , int val){
	if(l > v || r < u) return;
	if(u <= l && r <= v){
		stadd[idx] = max(stadd[idx] , val);
		st[idx].second = max(st[idx].second , st[idx].first + val);
		return;
	}
	int mid = (l + r) / 2;
	update(2 * idx , l , mid , u , v, val);
	update(2 * idx + 1 , mid + 1 , r , u , v , val);
	st[idx].second = max({st[2 * idx].second , st[2 * idx + 1].second , st[idx].first + stadd[idx]});
}

pii get(int idx , int l , int r , int u , int v){
	if(l > v || r < u) return {0 , 0};
	if(u <= l && r <= v) return st[idx];
	int mid = (l + r) / 2;
	pii t1 = get(2 * idx , l , mid  , u , v);
	pii t2 = get(2 * idx + 1 , mid + 1 , r , u , v);
	return make_pair(max(t1.first , t2.first) , max({t1.second , t2.second , max(t1.first, t2.first) + stadd[idx]}));
}


void upd(int l , int r){
	int pos = r * 2 - l;
	if(pos > n) return;
	update(1 , 1 , n , pos , n , a[l] + a[r]);
}

void emconhoanhko(void){
	stack<int> s;
	for(int i = n ; i >= 1 ; i--){
	    while(s.size() && a[i] >= a[s.top()]){
	    	upd(i , s.top());
	    	s.pop();
		}
		if(s.size()) upd(i , s.top());
		s.push(i);
		for(auto x : queries[i]) res[x.second] = get(1 , 1 , n , i , x.first).second;
	}


}



void solve(void){
	cin >> n; for(int i = 1 ; i <= n ; i++) cin >> a[i];
	cin >> q;
	for(int i = 1 ; i <= q; i++){
		 int l , r; cin >> l >> r;
		 queries[l].push_back({r , i});
	}
	build(1 , 1 , n);
	emconhoanhko();
	for(int i = 1 ; i <= q ; i++) cout << res[i] << endl;
	
}

signed main(void){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	solve();
	return 0;
}

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