Submission #944315

#	Time	Username	Problem	Language	Result	Execution time	Memory
944315		LCJLY	Triple Jump (JOI19_jumps)	C++14	100 / 100	888 ms	155636 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int arr[500005];
struct node{
	int s,e,m;
	node *l,*r;
	int v,lazyMax,hold;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyMax(0),hold(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			v=max(l->v,r->v);
		}
		else v=arr[s];
	}
	
	void self_change(int x){
		lazyMax=max(lazyMax,x);
		hold=max(hold,v+x);
	}
	
	void forceProp(){
		if(s==e) return;
		l->self_change(lazyMax);
		r->self_change(lazyMax);
	}
	
	void rangeUpd(int x, int y, int c){
		if(x>y) return;
		if(x<=s&&y>=e){
			self_change(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		hold=max(l->hold,r->hold);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e) return hold;
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return max(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){
	int n;
	cin >> n;
	for(int x=1;x<=n;x++){
		cin >> arr[x];
	}
	
	vector<int>adj[n+5];
	deque<int>d;
	for(int x=1;x<=n;x++){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()){
			adj[d.back()].push_back(x);
		}
		d.push_back(x);
	}
	
	d.clear();
	for(int x=n;x>=1;x--){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()){
			adj[x].push_back(d.back());
		}
		d.push_back(x);
	}
	
	node st(0,n);
	
	int q;
	cin >> q;
	vector<pii>que[n+5];
	int temp,temp2;
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		que[temp].push_back({temp2,x});
	}
	
	int ans[q];
	
	for(int x=n;x>=1;x--){
		for(auto it:adj[x]){
			int hold=arr[it]+arr[x];
			//show2(2*it-x,2*it-x,hold,hold);
			st.rangeUpd(2*it-x,n,hold);
		}
		for(auto it:que[x]){
			int index=it.second;
			int r=it.first;
			ans[index]=st.query(x,r);
		}
		
		//for(int y=1;y<=n;y++){
			//cout << st.query(y,y) << " ";
 		//}
 		//cout <<  " st" << endl;
	}
	
	for(int x=0;x<q;x++){
		cout << ans[x] << "\n";
	}	
}	

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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