Submission #980613

#	Time	Username	Problem	Language	Result	Execution time	Memory
980613		Dzadzo	Triple Jump (JOI19_jumps)	C++17	100 / 100	988 ms	111096 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 300000
using namespace std;
int t[4*MAXN+1],lazy[4*MAXN+1],ans[4*MAXN+1];
void build(int v,int tl,int tr,int a[]){
	if (tl==tr)t[v]=ans[v]=a[tl];else{
		int tm=(tl+tr)/2;
		build(v*2,tl,tm,a);
		build(v*2+1,tm+1,tr,a);
		t[v]=max(t[v*2],t[v*2+1]);
		ans[v]=max(ans[v*2],ans[v*2+1]);
	}
}
void push(int v){
	ans[2*v]=max(ans[2*v],t[2*v]+lazy[v]);
	ans[2*v+1]=max(ans[2*v+1],t[2*v+1]+lazy[v]);
	lazy[2*v]=max(lazy[2*v],lazy[v]);
	lazy[2*v+1]=max(lazy[2*v+1],lazy[v]);
	lazy[v]=0;
}
void up(int v,int tl,int tr,int l,int r,int delta){
	if (l>r)return;
	if (tl==l && tr==r){
		ans[v]=max(ans[v],t[v]+delta);
		lazy[v]=max(lazy[v],delta);
	}else{
		push(v);
		int tm=(tl+tr)/2;
		up(v*2,tl,tm,l,min(r,tm),delta);
		up(v*2+1,tm+1,tr,max(l,tm+1),r,delta);
		ans[v]=max(ans[2*v],ans[2*v+1]);
	}
}
int get(int v,int tl,int tr,int l,int r){
	if (l>r)return 0;
	if (tl==l && tr==r)return ans[v];
	push(v);
	int tm=(tl+tr)/2;
	return max(get(v*2,tl,tm,l,min(r,tm)),get(v*2+1,tm+1,tr,max(l,tm+1),r));
}
signed main(){	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n;
	cin>>n;
	int a[n+1];
	for (int i=1;i<=n;i++)cin>>a[i];
	stack <int> s;
	vvi inds(n+1);
	for (int i=1;i<=n;i++){
		while (!s.empty() && a[s.top()]<a[i])s.pop();
		if (!s.empty()){
			if (2*i-s.top()<=n)inds[s.top()].pb(i);
		}
		s.push(i);
		inds[i].pb(i+1);
	}
	while(!s.empty())s.pop();
	for (int i=n;i>=1;i--){
		while (!s.empty() && a[s.top()]<a[i])s.pop();
		if (!s.empty()){
			if (2*s.top()-i<=n)inds[i].pb(s.top());
		}
		s.push(i);		
	}
	build(1,1,n,a);
	int q;
	cin>>q;
	vvp R(n+1);
	for (int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		R[l].pb({r,i});
	}
	int res[q+1];
	for (int i=n;i>=1;i--){
		for (int x:inds[i])up(1,1,n,2*x-i,n,a[x]+a[i]);
		for (auto &[r,id]:R[i])res[id]=get(1,1,n,i,r);
	}
	for (int i=1;i<=q;i++)cout<<res[i]<<'\n';
}

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