Submission #1222336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222336		thangdz2k7	Triple Jump (JOI19_jumps)	C++20	100 / 100	657 ms	48936 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int MAX = 5e5 + 5;

int n, a[MAX], q, ans[MAX];
vector <pair <int, int>> queries[MAX];
int Max_cur[MAX << 2], Max_add[MAX << 2], Max_val[MAX << 2];

void build(int s, int l, int r){
	if (l == r){
		Max_cur[s] = a[l];
		Max_val[s] = a[l];
		return;
	}

	int mid = l + r >> 1;

	build(s << 1, l, mid);
	build(s << 1 | 1, mid + 1, r);

	Max_cur[s] = max(Max_cur[s << 1], Max_cur[s << 1 | 1]);
	Max_val[s] = Max_cur[s];

}

void update(int u, int v, int val, int s = 1, int l = 1, int r = n){
	if (u <= l && r <= v){
		Max_add[s] = max(Max_add[s], val);
		Max_val[s] = max(Max_val[s], Max_cur[s] + val);
		return;
	}

	int mid = l + r >> 1;
	if (mid >= u) update(u, v, val, s << 1, l, mid);
	if (mid < v) update(u, v, val, s << 1 | 1, mid + 1, r);

	Max_val[s] = max({Max_val[s << 1], Max_val[s << 1 | 1], Max_cur[s] + Max_add[s]});

}

pair <int, int> get(int u, int v, int s = 1, int l = 1, int r = n){
	if (v < l || u > r) return make_pair(0, 0);
	if (u <= l && r <= v) return make_pair(Max_val[s], Max_cur[s]);

	int mid = l + r >> 1;
	auto [a, b] = get(u, v, s << 1, l, mid);
	auto [c, d] = get(u, v, s << 1 | 1, mid + 1, r);

	return make_pair(max({a, c, max(b, d) + Max_add[s]}), max(b, d));
}

void process(){
	cin >> n; 
	for (int i = 1; i <= n; ++ i) 
		cin >> a[i];

	build(1, 1, n);

	cin >> q;
	for (int i = 1; i <= q; ++ i){
		int l, r; cin >> l >> r;
		queries[l].emplace_back(r, i);
	}

	auto add = [&](int i, int j) -> void {
		int k = j + (j - i);
		if (k > n) return;
		update(k, n, a[i] + a[j]);
	};

	vector <int> stk = {n};
	for (int l = n - 1; l >= 1; -- l){
		while (stk.size() && a[l] >= a[stk.back()]){
			add(l, stk.back());
			stk.pop_back();
		}
		if (stk.size()) add(l, stk.back());
		stk.push_back(l);

		for (auto [r, id] : queries[l]) ans[id] = get(l, r).first;
	}

	for (int i = 1; i <= q; ++ i)
		cout << ans[i] << "\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	process();
	return 0;

}

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