Submission #981024

#	Time	Username	Problem	Language	Result	Execution time	Memory
981024		NintsiChkhaidze	Triple Jump (JOI19_jumps)	C++17	100 / 100	1463 ms	112068 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
// #pragma GCC optimize("Ofast")
using namespace std;
 
const int N = 5e5 + 3;
vector <pii> qr[N];
vector <int> pr[N];
int a[N],told[4*N],tnew[4*N],lz[4*N];
int ans[N];

void build(int h,int l,int r){
	if (l == r){
		told[h] = tnew[h] = a[l];
		return;
	}

	build(left);
	build(right);
	told[h] = tnew[h] = max(told[h*2],told[h*2+1]);
}

void push(int h){
	if (lz[h]==0) return;
	lz[h*2]=max(lz[h*2],lz[h]);
	lz[h*2+1] = max(lz[h*2+1],lz[h]);
	tnew[h*2] = max(tnew[h*2],told[h*2] + lz[h]);
	tnew[h*2+1] = max(tnew[h*2+1],told[h*2+1] + lz[h]);
	lz[h]=0;
}

void upd(int h,int l,int r,int L,int R,int val){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		tnew[h] = max(tnew[h],val + told[h]);
		lz[h] = max(lz[h],val);
		return;
	}

	push(h);
	upd(left,L,R,val);
	upd(right,L,R,val);
	tnew[h] = max(tnew[h*2],tnew[h*2+1]);
}

int get(int h,int l,int r,int L,int R){
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return tnew[h];
	push(h);
	return max(get(left,L,R),get(right,L,R));
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n;
	cin>>n;

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	build(1,1,n);
	int q;
	cin>>q;

	for (int i = 1; i <= q; i++){
		int l,r;
		cin>>l>>r;
		qr[l].pb({r,i});
	}

	vector <int> st;
	for (int i = 1; i <= n; i++){
		while (st.size() && a[i] >= a[st.back()]){
			pr[st.back()].pb(i);
			st.pop_back();
		}

		if (st.size()) pr[st.back()].pb(i);
		st.pb(i);
	}

	for (int i = n; i >= 1; i--){
		for (int j: pr[i]){
			int l = 2*j - i,r = n;
			upd(1,1,n,l,r,a[i] + a[j]);
		}

		for (auto c: qr[i]){
			ans[c.s] = get(1,1,n,i,c.f);
		}
	}

	for (int i = 1; i <= q; i++)
		cout<<ans[i]<<endl;
}	

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