Submission #242376

#	Time	Username	Problem	Language	Result	Execution time	Memory
242376		errorgorn	Triple Jump (JOI19_jumps)	C++14	100 / 100	990 ms	111420 KiB

jumps

//雪花飄飄北風嘯嘯
//天地一片蒼茫
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
 
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int n,q;
ll arr[500005];
 
vector<int> stk;
 
vector<ii> good;
 
struct Q{
	int l,r;
	int idx;
	
	Q(int a,int b,int c){
		l=a,r=b,idx=c;
	}
};
 
vector<Q> queries;
 
ll ans[500005];
 
struct dat{
	ll ab=-1e18,c=0,abc=0;
};
 
dat merge(dat i,dat j){
	dat res;
	
	res.c=max(i.c,j.c);
	res.ab=max(i.ab,j.ab);
	res.abc=MAX(i.abc,j.abc,i.ab+j.c);
	
	return res;
}
 
struct node{
	int s,e,m;
	dat val;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			val=merge(l->val,r->val);
		}
		else{
			val.c=arr[s];
		}
	}
	
	void update(int i,ll j){
		if (s==e) val.ab=max(val.ab,j);
		else{
			if (i<=m) l->update(i,j);
			else r->update(i,j);
			
			val=merge(l->val,r->val);
		}
	}
	
	dat query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return merge(l->query(i,m),r->query(m+1,j));
	}
} *root;
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x];
	
	root=new node(0,500005);
	
	rep(x,0,n){
		while (!stk.empty() && arr[stk.back()]<=arr[x]){
			good.push_back({stk.back(),x});
			stk.pop_back();
		}
		
		if (!stk.empty()) good.push_back({stk.back(),x});
		stk.push_back(x);
	}
	
	cin>>q;
	int a,b;
	rep(x,0,q){
		cin>>a>>b;
		a--,b--;
		queries.push_back(Q(a,b,x));
	}
	
	sort(all(good),[](ii i,ii j){
		return i.fi<j.fi;
	});
	
	sort(all(queries),[](Q &i,Q &j){
		return i.l>j.l;
	});
	
	for (auto &it:queries){
		while (!good.empty() && it.l<=good.back().fi){
			int pos=good.back().se*2-good.back().fi-1;
			
			//cout<<pos<<" "<<good.back().fi<<" "<<good.back().se<<endl;
			if (pos<500005) root->update(pos,arr[good.back().fi]+arr[good.back().se]);
			
			good.pop_back();
		}
		
		ans[it.idx]=root->query(0,it.r).abc;
	}
	
	rep(x,0,q) cout<<ans[x]<<endl;
}

Compilation message (stderr)

jumps.cpp: In constructor 'node::node(int, int)':
jumps.cpp:74:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

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