Submission #941021

#	Time	Username	Problem	Language	Result	Execution time	Memory
941021		pavement	Triple Jump (JOI19_jumps)	C++17	100 / 100	814 ms	122552 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

using ll = long long;
using ii = pair<int, int>;

int N, Q, A[500005], ans[500005];
vector<int> ev[500005];
vector<ii> qu[500005];
stack<int> st;

struct node {
	node *left, *right;
	int S, E, val, r_val, A_val, pv;
	node(int _s, int _e) : S(_s), E(_e), r_val(-(int)1e9), pv(-(int)1e9) {
		if (S == E) {
			A_val = A[S];
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
		A_val = max(left->A_val, right->A_val);
	}
	void prop() {
		left->r_val = max(left->r_val, pv + left->A_val);
		left->pv = max(left->pv, pv);
		right->r_val = max(right->r_val, pv + right->A_val);
		right->pv = max(right->pv, pv);
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) {
			return;
		}
		if (l <= S && E <= r) {
			r_val = max(r_val, v + A_val);
			pv = max(pv, v);
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		r_val = max(left->r_val, right->r_val);
	}
	int qry(int l, int r) {
		if (l > E || r < S) {
			return -(int)1e9;
		}
		if (l <= S && E <= r) {
			return r_val;
		}
		prop();
		return max(left->qry(l, r), right->qry(l, r));
	}
} *root;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	for (int i = N; i >= 1; i--) {
		while (!st.empty() && A[st.top()] < A[i]) {
			st.pop();
		}
		if (!st.empty()) {
			ev[i].pb(st.top());
		}
		st.push(i);
	}
	while (!st.empty()) {
		st.pop();
	}
	for (int i = 1; i <= N; i++) {
		while (!st.empty() && A[st.top()] < A[i]) {
			st.pop();
		}
		if (!st.empty()) {
			ev[st.top()].pb(i);
		}
		st.push(i);
	}
	cin >> Q;
	for (int i = 1, L, R; i <= Q; i++) {
		cin >> L >> R;
		qu[L].eb(R, i);
	}
	root = new node(1, N);
	for (int i = N; i >= 1; i--) {
		for (auto b : ev[i]) {
			// a = i
			root->upd(2 * b - i, N, A[i] + A[b]);
		}
		for (auto [r, idx] : qu[i]) {
			ans[idx] = root->qry(1, r);
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << ans[i] << '\n';
	}
}

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