Submission #941711

#	Time	Username	Problem	Language	Result	Execution time	Memory
941711		emptypringlescan	Triple Jump (JOI19_jumps)	C++17	100 / 100	656 ms	138728 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long arr[500005];
struct node{
	int s,e,m;
	long long val,con,suf;
	node *l, *r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		con=-1e16;
		suf=arr[s];
		if(s!=e){
			l=new node(S,m);
			r=new node(m+1,E);
			suf=max(l->suf,r->suf);
		}
		val=con+suf;
	}
	void update(int S, long long V){
		if(s==e){
			con=max(con,V);
			val=con+suf;
			return;
		}
		if(S<=m) l->update(S,V);
		else r->update(S,V);
		con=max(l->con,r->con);
		val=max({l->val,r->val,l->con+r->suf});
	}
	pair<long long,pair<long long,long long> > query(int S, int E){
		if(S<=s&&e<=E) return {val,{con,suf}};
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else{
			pair<long long,pair<long long,long long> > a=l->query(S,m),b=r->query(m+1,E),ret;
			ret.first=max({a.first,b.first,a.second.first+b.second.second});
			ret.second.first=max(a.second.first,b.second.first);
			ret.second.second=max(a.second.second,b.second.second);
			return ret;
		}
	}
} *root;
int32_t main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    root=new node(0,n-1);
    int q;
    cin >> q;
    vector<pair<long long,int> > mono;
    vector<pair<pair<int,int>,long long> > yay;
    for(int i=0; i<n; i++){
		while(!mono.empty()&&mono.back().first<=arr[i]){
			int a=mono.back().second;
			if(i*2-a<n) yay.push_back({{a,i*2-a},arr[a]+arr[i]});
			mono.pop_back();
		}
		if(!mono.empty()){
			int a=mono.back().second;
			if(i*2-a<n) yay.push_back({{a,i*2-a},arr[a]+arr[i]});
		}
		mono.push_back({arr[i],i});
	}
	sort(yay.begin(),yay.end());
	pair<pair<int,int>,int> qu[q];
	for(int i=0; i<q; i++){
		cin >> qu[i].first.first >> qu[i].first.second;
		qu[i].first.first--; qu[i].first.second--;
		qu[i].second=i;
	}
	sort(qu,qu+q,greater<pair<pair<int,int>,int> >());
	long long ans[q];
	for(int i=0; i<q; i++){
		while(!yay.empty()&&yay.back().first.first>=qu[i].first.first){
			root->update(yay.back().first.second,yay.back().second);
			yay.pop_back();
		}
		ans[qu[i].second]=root->query(0,qu[i].first.second).first;
	}
	for(int i=0; i<q; i++) cout << ans[i] << '\n';
}
/*15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81 
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13*/

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