Submission #329841

#	Time	Username	Problem	Language	Result	Execution time	Memory
329841		GioChkhaidze	Triple Jump (JOI19_jumps)	C++14	100 / 100	1321 ms	90500 KiB

jumps

#include <bits/stdc++.h>

#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define F first
#define S second

using namespace std;

const int N=5e5+5;

int n,q;
int a[N],ans[N];
deque < int > dq;
vector < pair < int , int > > Q[N],E[N];

typedef struct { int li; int r; int ans; } node;

node v[4*N];

void B(int h) {
	v[h].ans=max(v[h].ans,v[h].li+v[h].r);
	return ;
}

void Shift(Tree) {
	v[(h<<1)].li=max(v[(h<<1)].li,v[h].li);
	v[((h<<1)|1)].li=max(v[((h<<1)|1)].li,v[h].li);
	B((h<<1)),B(((h<<1)|1));
}

void Upd(Tree,int L,int R,int vl) {
	if (r<L || R<l) return ;
	if (L<=l && r<=R) {
		v[h].li=max(v[h].li,vl);
		B(h);
		return ;
	}
	
	Shift(h,l,r);
	Upd(Left,L,R,vl);
	Upd(Right,L,R,vl);
	v[h].ans=max(v[(h<<1)].ans,v[((h<<1)|1)].ans);
}

int L,R;
int get(Tree) {
	if (r<L || R<l) return 0;
	if (L<=l && r<=R) return v[h].ans;
	Shift(h,l,r);
	int x=get(Left);
	int y=get(Right);
	return max(x,y);
}

void Build(Tree) {
	if (l==r) {
		v[h].r=a[r];
		return ;
	}
	
	Build(Left);
	Build(Right);
	v[h].r=max(v[(h<<1)].r,v[((h<<1)|1)].r);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	
	cin>>n;
	
	a[0]=1e8+1;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
	}

	dq.push_back(0);
	for (int l,i=1,r; i<=n; i++) {
		while (a[dq.back()]<a[i]) 
			dq.pop_back();
		
		l=dq.back();	
		if (l) {
			r=i+i-l;
			if (r<=n) 
				E[l].push_back({r,a[l]+a[i]});
		}
	
		dq.push_back(i);
	}
	 
	while (dq.size()) dq.pop_back();
	
	dq.push_back(0);
	for (int l=n,i,r; l>=1; l--) {
		while (a[dq.back()]<a[l])
			dq.pop_back();
		
		i=dq.back();	
		if (i) {
			r=i+i-l;
			if (r<=n)
				E[l].push_back({r,a[l]+a[i]});
		}
		
		dq.push_back(l);
	}
	
	Build(1,1,n);
	
	cin>>q;
	for (int i=1; i<=q; i++) {
		int l,r;
		cin>>l>>r;
		Q[l].push_back({r,i});
	}
	
	for (L=n; L>=1; --L) {
		for (int j=0; j<E[L].size(); j++) {
			Upd(1,1,n,E[L][j].F,n,E[L][j].S);
		}
		
		for (int j=0; j<Q[L].size(); j++) {
			int id=Q[L][j].S;
			R=Q[L][j].F;
			ans[id]=get(1,1,n);
		}
	}
	
	for (int i=1; i<=q; i++)
		cout<<ans[i]<<"\n";
}

Compilation message (stderr)

jumps.cpp:68:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main () {
      |       ^
jumps.cpp: In function 'int main()':
jumps.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int j=0; j<E[L].size(); j++) {
      |                 ~^~~~~~~~~~~~
jumps.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for (int j=0; j<Q[L].size(); j++) {
      |                 ~^~~~~~~~~~~~

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