Submission #242269

#	Time	Username	Problem	Language	Result	Execution time	Memory
242269		oolimry	Triple Jump (JOI19_jumps)	C++14	100 / 100	1055 ms	131136 KiB

jumps

#include <bits/stdc++.h>
#define a first
#define b second
#define ab first
#define value second
#define r first
#define id second
#define int long long
using namespace std;
typedef pair<int,int> ii;

const int inf = 102345678901;
const int N = 1<<19;
int arr[N];
int ans[N];
vector<ii> updates[N];
vector<ii> queries[N];

struct node{ int c, ab, abc; };
node tree[2*N];

node relax(node L, node R){
	return { max(L.c, R.c), max(L.ab, R.ab), max(L.ab+R.c, max(L.abc, R.abc)) };
}

void init(){
	for(int i = N;i < 2*N;i++) tree[i] = {arr[i-N], -inf, -inf};
	for(int i = N-1;i >= 1;i--) tree[i] = relax(tree[i<<1], tree[i<<1|1]);
}

void update(int i, int ab){
	i += N;
	
	tree[i].ab = max(tree[i].ab, ab);
	tree[i].abc = max(tree[i].ab + tree[i].c, tree[i].abc);
	
	for(i >>= 1;i > 0;i >>= 1) tree[i] = relax(tree[i<<1], tree[i<<1|1]);
}

int query(int l, int r){
	node L = {-inf,-inf,-inf};
	node R = {-inf,-inf,-inf};
	
	for(l += N, r += N;l < r;l >>= 1, r >>= 1){
		if(l&1) L = relax(L, tree[l++]);
		if(r&1) R = relax(tree[--r], R);
	}
	
	return relax(L,R).abc;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	for(int i = 0;i < n;i++) cin >> arr[i];
	
	vector<ii> goodpairs;
	stack<int> S;
	for(int i = 0;i < n;i++){
		while(!S.empty()){
			int top = S.top();
			goodpairs.push_back(ii(top,i));
			
			if(arr[i] >= arr[top]) S.pop();
			else break;
		}
		S.push(i);
	}
	
	for(ii p : goodpairs){
		int ab = p.b * 2 - p.a;
		if(ab < n) updates[p.a].push_back(ii(ab, arr[p.a] + arr[p.b]));
	}
	
	int Q; cin >> Q;
	
	for(int q = 0;q < Q;q++){
		int l, r; cin >> l >> r; l--; r--;
		queries[l].push_back(ii(r,q));
	}
	
	init();
	
	for(int l = n-1;l >= 0;l--){
		for(ii u : updates[l]){
			update(u.ab, u.value);
		}
		
		for(ii q : queries[l]){
			int r = q.r;
			ans[q.id] = query(l, r+1);
		}
	}
	
	for(int q = 0;q < Q;q++) cout << ans[q] << "\n";
}

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