Submission #722151

#	Time	Username	Problem	Language	Result	Execution time	Memory
722151		Radin_Zahedi2	Triple Jump (JOI19_jumps)	C++17	100 / 100	1025 ms	87820 KiB

jumps

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n, q;
const int N = 5e5 + 5;
const int L = (1 << 20);
int a[N];

vector<int> bigs[N];
vector<pair<int, int>> quer[N];

int seg[L][3];

void cre(int l, int r, int ind) {
	if (l == r) {
		seg[ind][0] = -inf;
		seg[ind][1] = -inf;
		seg[ind][2] = a[l];
		return;
	}

	int m = (l + r) / 2;
	cre(l, m, 2 * ind);
	cre(m + 1, r, 2 * ind + 1);

	seg[ind][0] = -inf;
	seg[ind][1] = -inf;
	seg[ind][2] = max(seg[2 * ind][2], seg[2 * ind + 1][2]);
}

void upd(int b, int x, int l, int r, int ind) {
	if (b <= l) {
		seg[ind][1] = max(seg[ind][1], x);
		seg[ind][0] = max(seg[ind][0], seg[ind][1] + seg[ind][2]);
		return;
	}
	if (r < b) {
		return;
	}

	int m = (l + r) / 2;
	upd(b, x, l, m, 2 * ind);
	upd(b, x, m + 1, r, 2 * ind + 1);

	seg[ind][0] = max(seg[ind][0], max(seg[2 * ind][0], seg[2 * ind + 1][0]));
}

pair<int, int> get(int b, int e, int l, int r, int ind) {
	if (b <= l && r <= e) {
		return mp(seg[ind][0], seg[ind][2]);
	}
	if (e < l || r < b) {
		return mp(-inf, 0);
	}

	
	int m = (l + r) / 2;

	pair<int, int> p1 = get(b, e, l, m, 2 * ind);
	pair<int, int> p2 = get(b, e, m + 1, r, 2 * ind + 1);

	return mp(max(seg[ind][1] + max(p1.se, p2.se), max(p1.fi, p2.fi)), max(p1.se, p2.se));
}

void init() {
}

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

	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;

		quer[l].pb(mp(r, i));
	}
}

void solve() {
	vector<int> big;
	for (int i = n; i >= 1; i--) {
		while (!big.empty()) {
			int x = big.back();

			if (a[i] <= a[x]) {
				break;
			}

			bigs[i].pb(x);
			big.pop_back();
		}

		if (!big.empty()) {
			bigs[i].pb(big.back());
		}
		big.pb(i);
	}


	cre(1, n, 1);

	int ans[q + 1];
	for (int l = n; l >= 1; l--) {
		for (auto i : bigs[l]) {
			upd(2 * i - l, a[l] + a[i], 1, n, 1);
		}

		for (auto p : quer[l]) {
			ans[p.se] = get(l, p.fi, 1, n, 1).fi;
		}
	}


	for (int i = 1; i <= q; i++) {
		cout << ans[i] << endl;
	}
}

void output() {
}

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

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

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