Submission #296873

#	Time	Username	Problem	Language	Result	Execution time	Memory
296873		YJU	Triple Jump (JOI19_jumps)	C++14	100 / 100	1492 ms	126696 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=1e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll seg[4*N],tag[4*N],n,u[N],m,lst,ans[N],pseg[4*N];
vector<pll> upd[N];
pair<pll,ll> q[N];
stack<pll> stk;

void push(ll id){
	tag[id*2]=max(tag[id*2],tag[id]);
	tag[id*2+1]=max(tag[id*2+1],tag[id]);
	seg[id*2]=max(seg[id*2],pseg[id*2]+tag[id*2]);seg[id*2+1]=max(seg[id*2+1],pseg[id*2+1]+tag[id*2+1]);
}

void add(ll id,ll l,ll r,ll ql,ll qr,ll D){
	if(l>=ql&&r<=qr){
		tag[id]=max(tag[id],D);
		push(id);
		seg[id]=max(seg[id*2],seg[id*2+1]);
		seg[id]=max(seg[id],pseg[id]+tag[id]);
		//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
		return ;
	}
	if(l>=qr||r<=ql)return ;
	push(id);
	ll mid=(l+r)/2;
	add(id*2,l,mid,ql,qr,D);
	add(id*2+1,mid,r,ql,qr,D);
	seg[id]=max(seg[id*2],seg[id*2+1]);
	//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
}

void pins(ll id,ll l,ll r,ll to,ll D){
	if(l==r-1){pseg[id]=max(pseg[id],D);return ;}
	ll mid=(l+r)/2;
	if(to<mid){
		pins(id*2,l,mid,to,D);
	}else{
		pins(id*2+1,mid,r,to,D);
	}
	pseg[id]=max(pseg[id*2],pseg[id*2+1]);
}

ll Q(ll id,ll l,ll r,ll ql,ll qr){
	//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
	if(l>=ql&&r<=qr)return seg[id];
	if(l>=qr||r<=ql)return 0;
	push(id);
	ll mid=(l+r)/2;
	return max(Q(id*2,l,mid,ql,qr),Q(id*2+1,mid,r,ql,qr));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	lst=n;
	REP1(i,n)cin>>u[i],pins(1,1,n+1,i,u[i]);
	REP1(i,n){
		while(SZ(stk)&&stk.top().X<=u[i]){
			upd[stk.top().Y].pb(mp(i,stk.top().X+u[i]));
			stk.pop();
		}
		if(SZ(stk)){upd[stk.top().Y].pb(mp(i,stk.top().X+u[i]));}
		stk.push(mp(u[i],i));
	}
	cin>>m;
	REP(i,m)cin>>q[i].X.X>>q[i].X.Y,q[i].Y=i;
	sort(q,q+m,[](pair<pll,ll> A,pair<pll,ll> B){
		return (A.X.X>B.X.X);
	});
	REP(i,m){
		//cout<<"que : "<<q[i].X.X<<" "<<q[i].X.Y<<"\n";
		while(lst>=q[i].X.X){
			for(auto j:upd[lst]){
				if(j.X+j.X-lst>=n+1)continue;
				//cout<<"upd : "<<j.X<<" "<<2*j.X-lst<<" "<<j.Y<<"\n";
				add(1,1,n+1,2*j.X-lst,n+1,j.Y);
			}
			--lst;
		}
		ans[q[i].Y]=Q(1,1,n+1,q[i].X.X+2,q[i].X.Y+1);
	}
	REP(i,m)cout<<ans[i]<<"\n";
	return 0;
}
/*
5
5 2 1 5 3
3
1 5
2 5
1 4
*/

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