제출 #284515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284515		kshitij_sodani	Triple Jump (JOI19_jumps)	C++14	100 / 100	1754 ms	100856 KiB

jumps

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n' 

llo n;
llo it[500001];
vector<pair<llo,llo>> tt[500001];
llo tree[4*500001];
llo tree2[4*500001];
llo lazy[4*500001];
llo ans[500001];
void build(llo no,llo l,llo r){
	if(l==r){
		tree2[no]=it[l];
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
	}
}
void push(llo no,llo l,llo r){
	tree[no]=max(tree[no],tree2[no]+lazy[no]);
	if(l<r){
		lazy[no*2+1]=max(lazy[no*2+1],lazy[no]);
		lazy[no*2+2]=max(lazy[no*2+2],lazy[no]);
	}
	lazy[no]=0;

}
void update(llo no,llo l,llo r,llo aa,llo bb,llo val){
	push(no,l,r);
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		tree[no]=max(tree[no],val+tree2[no]);
		if(l<r){
			lazy[no*2+1]=max(lazy[no*2+1],val);
			lazy[no*2+2]=max(lazy[no*2+2],val);
		}
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,val);
		update(no*2+2,mid+1,r,aa,bb,val);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
	push(no,l,r);
	if(r<aa or l>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		llo mid=(l+r)/2;
		return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
	}

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	vector<pair<llo,llo>> ss;


	for(llo i=0;i<n;i++){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		if(ss.size()){
			llo ind=i-ss.back().b+i;
			if(ind<n){
				tt[ss.back().b].pb({i,-1});

				//ans=max(ans,it[i]+ss.back().a+aa[ind]);
			}
		}
		ss.pb({it[i],i});
	}
	ss.clear();
	for(llo i=n-1;i>=0;i--){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		if(ss.size()){
			llo ind=ss.back().b-i+ss.back().b;
			if(ind<n){
				tt[i].pb({ss.back().b,-1});
				//ans=max(ans,it[i]+ss.back().a+aa[ind]);
			}
		}
		ss.pb({it[i],i});
	}
	llo q;
	cin>>q;
	for(llo i=0;i<q;i++){
		llo cc,dd;
		cin>>cc>>dd;
		cc--;
		dd--;
		tt[cc].pb({dd,i});
	}
	build(0,0,n-1);

	for(llo i=n-1;i>=0;i--){
		for(auto j:tt[i]){
			//cout<<i<<":"<<j.a<<":"<<j.b<<endl;
			if(j.b==-1){
				llo ind=j.a+j.a-i;
				//cout<<ind<<":"<<i<<","<<j.a<<":"<<it[j.a]+it[i]<<endl;
				update(0,0,n-1,ind,n-1,it[j.a]+it[i]);
			}
			else{
				ans[j.b]=query(0,0,n-1,i,j.a);
				//cout<<j.b<<endl;
			}
		}


	}






	for(llo i=0;i<q;i++){
		cout<<ans[i]<<'\n';
	}






 
	return 0;
}

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