Submission #1087219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087219		peacebringer1667	Triple Jump (JOI19_jumps)	C++17	100 / 100	659 ms	104532 KiB

jumps

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
#define usa unsigned int
#define pirusa pair <unsigned int,unsigned int>
using namespace std;
const int maxn = 5e5 + 5;

template <typename T> void maxi(T &x,T y){x = max(x,y);}
struct segment_tree{
	unsigned int seg[4*maxn],lazy[4*maxn],base[4*maxn];
	
	void downlazy(int v,int l,int r){
		if (!lazy[v]) return;
		seg[v] = max(seg[v],base[v] + lazy[v]);
		
		if (l != r){
			maxi(lazy[2*v + 1],lazy[v]);
			maxi(lazy[2*v + 2],lazy[v]); 
		}
		lazy[v] = 0;
	}
	
	void base_update(int l,int r,int v,int p,int val){
		if (l > p || r < p) return;
		if (l == r){
			base[v] = val;
			return;
		}
		
		int w = (l + r)/2;
		base_update(l,w,2*v + 1,p,val);
		base_update(w + 1,r,2*v + 2,p,val);
		base[v] = max(base[2*v + 1],base[2*v + 2]);
	}
	
	void update(int l,int r,int v,int lx,int rx,unsigned int val){
		downlazy(v,l,r);
		if (l > rx || r < lx) return;
		if (l >= lx && r <= rx){
			lazy[v] = max(lazy[v],val);
			downlazy(v,l,r);
			return;
		}
		
		int w = (l + r)/2;
		update(l,w,2*v + 1,lx,rx,val);
		update(w + 1,r,2*v + 2,lx,rx,val);
		seg[v] = max(seg[2*v + 1],seg[2*v + 2]);
	}
	
	unsigned int calc(int l,int r,int v,int lx,int rx){
		downlazy(v,l,r);
		if (l > rx || r < lx) return 0;
		if (l >= lx && r <= rx) return seg[v];
		
		int w = (l + r)/2;
		return max(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
	}
} seg;

vector <vector<pirusa>> vec(maxn);
usa res[maxn];
int a[maxn],L[maxn],R[maxn];
vector <vector<pir>> Q(maxn);
////////
int input(int n){
	int q;
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	cin >> q;
	for (int i = 1 ; i <= q ; i++){
		cin >> L[i] >> R[i];
	}
	return q;
}
namespace sub1{
	const int N = 5e3 + 5;
	
	bool check(int n,int q){
		return (n <= 5000);
	}
	
	unsigned int f[N][N];
	
	void prepare(int n){
		for (int l = 1 ; l < n - 1 ; l++){
			int x = a[l + 1];
			for (int r = l + 2 ; r <= n ; r++){
				x = max(x,a[(l + r)/2]);
				f[l][r] = max(f[l][r],(unsigned int)(a[l] + x + a[r]));
			}
		}
		
		for (int len = 3 ; len <= n ; len++)
		  for (int i = 1 ; i <= n - len + 1 ; i++){
		  	int l = i,r = i + len - 1;
		  	f[l][r] = max(f[l][r],max(f[l + 1][r],f[l][r - 1]));
		  }
	}
	
	void solve(int n,int q){
		prepare(n);
		
		for (int i = 1 ; i <= q ; i++)
		  cout << f[L[i]][R[i]] << "\n";
	}
}
///////


void prepare(int n){
	deque <int> dq;
	
	for (int i = n ; i > 0 ; i--){
		while (dq.size()){
			int l = i,r = dq.back();
		    
		    if (2*r - l <= n)
		      vec[l].push_back({2*r - l,(usa)a[i] + (usa)a[dq.back()]});
			
			if (a[dq.back()] <= a[i])
			  dq.pop_back();
		    else break;
		}
		
		dq.push_back(i);
	}
	
	for (int i = 1 ; i <= n ; i++)
	  seg.base_update(1,n,0,i,a[i]);
}

void prepare_query(int q){
	for (int i = 1 ; i <= q ; i++)
	  Q[L[i]].push_back({R[i],i});
}

void solve(int n,int q){
	for (int i = n ; i > 0 ; i--){
		for (pirusa P : vec[i]){
			int l = P.fi;usa val = P.se;
			seg.update(1,n,0,l,n,val);
		}
		
		for (pir query : Q[i]){
			int l = i,r = query.fi,id = query.se;
			res[id] = seg.calc(1,n,0,l,r);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("JUMP.inp","r",stdin);
//	freopen("JUMP.out","w",stdout);
	int n,q;
	cin >> n;
	q = input(n);
	
	if (sub1::check(n,q)){
		sub1::solve(n,q);
		return 0;
	}
	
	prepare(n);
	prepare_query(q);
	solve(n,q);
	
	for (int i = 1 ; i <= q ; i++) cout << res[i] << "\n";

	return 0;
}

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