Submission #524882

#	Time	Username	Problem	Language	Result	Execution time	Memory
524882		valerikk	Triple Jump (JOI19_jumps)	C++17	100 / 100	924 ms	87864 KiB

jumps

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 500500;

int t[4 * N];
int mx[4 * N];
int d[4 * N];

void apply(int v, int val) {
	d[v] = max(d[v], val);
	t[v] = max(t[v], mx[v] + val);
}

void push(int v) {
	apply(2 * v, d[v]);
	apply(2 * v + 1, d[v]);
}

void upd(int v, int l, int r, int L, int R, int val) {
	if (l >= R || r <= L) {
		return;
	}
	if (l >= L && r <= R) {
		apply(v, val);
		return;
	}
	push(v);
	int m = (l + r) / 2;
	upd(2 * v, l, m, L, R, val);
	upd(2 * v + 1, m, r, L, R, val);
	t[v] = max({mx[v] + d[v], t[2 * v], t[2 * v + 1]});
}

int get(int v, int l, int r, int L, int R) {
	if (l >= R || r <= L) {
		return (int) -1e9;
	}
	if (l >= L && r <= R) {
		return t[v];
	}
	push(v);
	int m = (l + r) / 2;
	return max(get(2 * v, l, m, L, R), get(2 * v + 1, m, r, L, R));
}

void build(int v, int l, int r, int a[N]) {
	if (r - l == 1) {
		t[v] = -1e9;
		mx[v] = a[l];
		d[v] = -1e9;
	} else {
		int m = (l + r) / 2;
		build(2 * v, l, m, a);
		build(2 * v + 1, m, r, a);
		mx[v] = max(mx[2 * v], mx[2 * v + 1]);
		d[v] = -1e9;
		t[v] = -1e9;
	}
}

int n;
int a[N];
vector<pair<int, int>> qr[N];
vector<int> e[N];
int q;
int ans[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;	
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		--l;
		qr[l].push_back({r, i});
	}
	vector<int> st;
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && a[st.back()] <= a[i]) {
			e[st.back()].push_back(i);
			st.pop_back();
		}
		if (!st.empty()) {
			e[st.back()].push_back(i);
		}
 		st.push_back(i);		
	}
	build(1, 0, n, a);
	for (int i = n - 1; i >= 0; --i) {
		for (int j : e[i]) {
			upd(1, 0, n, i + (j - i) * 2, n, a[i] + a[j]);
		}
		for (auto qq : qr[i]) {
			ans[qq.second] = get(1, 0, n, i, qq.first);
		}
	}
	for (int i = 0; i < q; ++i) {
		cout << ans[i] << "\n";
	}
}

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