Submission #1214919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214919		irmuun	Triple Jump (JOI19_jumps)	C++20	100 / 100	727 ms	125400 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=5e5+5;

ll n,q;
ll a[N];

struct node{
	ll l,r,v;
	node(){l=r=v=0;}
};

node d[4*N];

node comb(node a,node b){
	node c;
	c.l=max(a.l,b.l);
	c.r=max(a.r,b.r);
	c.v=max({a.v,b.v,a.l+b.r});
	return c;
}

struct segtree{
	ll n;
	segtree(ll n):n(n){
		build(1,1,n);
	}
	void build(ll v,ll l,ll r){
		if(l==r){
			d[v].l=0;
			d[v].r=a[l];
			d[v].v=a[l];
			return;
		}
		ll m=(l+r)>>1;
		build(v<<1,l,m);
		build(v<<1|1,m+1,r);
		d[v]=comb(d[v<<1],d[v<<1|1]);
	}
	void update(ll v,ll l,ll r,ll x,ll val){
		if(l==r){
			d[v].l=max(d[v].l,val);
			d[v].v=d[v].l+d[v].r;
			return;
		}
		ll m=(l+r)>>1;
		if(x<=m) update(v<<1,l,m,x,val);
		else update(v<<1|1,m+1,r,x,val);
		d[v]=comb(d[v<<1],d[v<<1|1]);
	}
	node query(ll v,ll l,ll r,ll L,ll R){
		if(R<L||R<l||r<L) return node();
		if(L<=l&&r<=R) return d[v];
		ll m=(l+r)>>1;
		return comb(query(v<<1,l,m,L,R),query(v<<1|1,m+1,r,L,R));
	}
};

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	// ak>=aj then (a,b,c)=(i,k,-) better
	// ai<=ak<=aj (a,b,c)=(k,j,-) better
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
	}
	stack<ll>s;
	vector<pair<ll,ll>>v[n+5];
	for(ll i=n;i>=1;i--){
		while(!s.empty()&&a[s.top()]<a[i]){
			ll j=s.top();
			v[i].pb({j,a[i]+a[j]});
			s.pop();
		}
		if(!s.empty()){
			ll j=s.top();
			v[i].pb({j,a[i]+a[j]});
		}
		s.push(i);
	}
	cin>>q;
	vector<pair<ll,ll>>ask[n+5];
	for(ll i=0;i<q;i++){
		ll l,r;
		cin>>l>>r;
		ask[l].pb({r,i});
	}
	segtree sg(n);
	vector<ll>ans(q);
	for(ll i=n;i>=1;i--){
		for(auto [j,sum]:v[i]){
			if(2*j-i<=n){
				sg.update(1,1,n,2*j-i,sum);
			}
		}
		for(auto [j,k]:ask[i]){
			ans[k]=(sg.query(1,1,n,i,j)).v;
		}
	}
	for(ll i=0;i<q;i++){
		cout<<ans[i]<<"\n";
	}
}

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