제출 #520899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520899		ymm	3단 점프 (JOI19_jumps)	C++17	100 / 100	901 ms	87840 KiB

jumps

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 500010;
const int inf = 5e8;
int arr[N];
int n, q;

namespace seg{
	int lzy[N<<2], mx[N<<2], mxc[N<<2];
	void tag(int i, int x){
		mx[i] = max(mx[i], mxc[i]+x);
		lzy[i] = max(lzy[i], x);
	}
	void ppg(int i){
		if(lzy[i]>-inf){
			tag(2*i+1, lzy[i]);
			tag(2*i+2, lzy[i]);
			lzy[i]=-inf;
		}
	}
	void init(int i=0, int b=0, int e=n){
		lzy[i]=-inf; mx[i]=-inf;
		if(e-b==1) {mxc[i] = arr[b]; return;}
		init(2*i+1,b,(b+e)/2);
		init(2*i+2,(b+e)/2,e);
		mxc[i] = max(mxc[2*i+1], mxc[2*i+2]);
	}
	void up(int l, int r, int x, int i=0, int b=0, int e=n){
		if(l<=b&&e<=r) return tag(i, x);
		if(r<=b||e<=l) return;
		ppg(i);
		up(l,r,x,2*i+1,b,(b+e)/2);
		up(l,r,x,2*i+2,(b+e)/2,e);
		mx[i] = max(mx[2*i+1], mx[2*i+2]);
	}
	int get(int l, int r, int i=0, int b=0, int e=n){
		if(l<=b&&e<=r) return mx[i];
		if(r<=b||e<=l) return -inf;
		ppg(i);
		return max(
			get(l,r,2*i+1,b,(b+e)/2),
			get(l,r,2*i+2,(b+e)/2,e)
		);
	}
}
//namespace seg{
//	int mx[N];
//	void init(){
//		Loop(i,0,N) mx[i] = -inf;
//	}
//	int get(int l, int r){
//		int ans=0;
//		Loop(i,l,r) ans = max(ans,mx[i]);
//		return ans;
//	}
//	void up(int l, int r, int x){
//		Loop(i,l,r) mx[i] = max(mx[i],x+arr[i]);
//	}
//}

vector<pii> ql[N];
vector<int> cand[N];
int ans[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop(i,0,n) cin >> arr[i];
	seg::init();

	vector<int> st;
	Loop(i,0,n){
		while(st.size() && arr[st.back()] < arr[i])
			st.pop_back();
		if(st.size())
			cand[st.back()].push_back(i);
		st.push_back(i);
	}
	st.clear();
	LoopR(i,0,n){
		while(st.size() && arr[st.back()] < arr[i])
			st.pop_back();
		if(st.size())
			cand[i].push_back(st.back());
		st.push_back(i);
	}

	cin >> q;
	Loop(i,0,q){
		int l, r;
		cin >> l >> r; --l;
		ql[l].push_back({i,r});
	}

	LoopR(i,0,n){
		for(int j : cand[i]){
//			cout << i << ' ' << j << '\n';
			if(2*j-i<n) seg::up(2*j-i,n,arr[i]+arr[j]);
		}
		for(auto [j, r] : ql[i]){
			ans[j] = seg::get(i,r);
		}
	}

	Loop(i,0,q) cout << ans[i] << '\n';
}

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