Submission #198185

#	Time	Username	Problem	Language	Result	Execution time	Memory
198185		HungAnhGoldIBO2020	Triple Jump (JOI19_jumps)	C++14	100 / 100	1348 ms	87900 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+2;
const int inf=1e9+7;
int ar[N],ans[N];
struct node{
	int lef=-inf,rig=-inf,ans=-inf;
} it[4*N];
vector<pair<int,int> > lis,query[N];
vector<int> upd_lis[N];
void get(int idx,int l,int r){
	it[idx].lef=max(it[2*idx].lef,it[2*idx+1].lef);
	it[idx].rig=max(it[2*idx].rig,it[2*idx+1].rig);
	it[idx].ans=max(it[2*idx].ans,max(it[2*idx+1].ans,it[2*idx].lef+it[2*idx+1].rig));
}
node merge(node a,node b){
	node ans;
	ans.lef=max(a.lef,b.lef);
	ans.rig=max(a.rig,b.rig);
	ans.ans=max(a.ans,max(b.ans,a.lef+b.rig));
	return ans;
}
void init(int idx,int l,int r){
	if(l==r){
		it[idx].rig=ar[l];
		return;
	}
	init(2*idx,l,(l+r)/2);
	init(2*idx+1,(l+r)/2+1,r);
	get(idx,l,r);
}
void upd(int idx,int l,int r,int pos,int val){
	if(l>pos||r<pos){
		return;
	}
	if(l==r){
		it[idx].lef=max(it[idx].lef,val);
		it[idx].ans=max(it[idx].ans,it[idx].lef+it[idx].rig);
		return;
	}
	upd(2*idx,l,(l+r)/2,pos,val);
	upd(2*idx+1,(l+r)/2+1,r,pos,val);
	get(idx,l,r);
}
node getmax(int idx,int l,int r,int lef,int rig){
	if(l>rig||r<lef){
		return node();
	}
	if(l>=lef&&r<=rig){
		return it[idx];
	}
	return merge(getmax(2*idx,l,(l+r)/2,lef,rig),getmax(2*idx+1,(l+r)/2+1,r,lef,rig));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,q;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		while(lis.size()){
			upd_lis[lis.back().second].push_back(i);
			if(lis.back().first>ar[i]){
				break;
			}
			else{
				lis.pop_back();
			}
		}
		lis.push_back({ar[i],i});
	}
	init(1,1,n);
	cin>>q;
	for(i=1;i<=q;i++){
		cin>>j>>k;
		query[j].push_back({k,i});
	}
	for(i=n;i>0;i--){
		for(j=0;j<upd_lis[i].size();j++){
			if(2*upd_lis[i][j]-i>n){
				continue;
			}
			upd(1,1,n,2*upd_lis[i][j]-i,ar[i]+ar[upd_lis[i][j]]);
		}
		for(j=0;j<query[i].size();j++){
			node wow=getmax(1,1,n,i,query[i][j].first);
			ans[query[i][j].second]=wow.ans;
		}
	}
	for(i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:79:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<upd_lis[i].size();j++){
           ~^~~~~~~~~~~~~~~~~~
jumps.cpp:85:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<query[i].size();j++){
           ~^~~~~~~~~~~~~~~~
jumps.cpp:57:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l,q;
              ^

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