Submission #1116243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116243		sinatbtfard	Triple Jump (JOI19_jumps)	C++17	100 / 100	1095 ms	142912 KiB

jumps

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 21, kaf = 1 << 20, inf = 1e15;

struct segment {
	int seg[1 << maxn], mx[1 << maxn], lazy[1 << maxn];
	segment (){
		for (int i = 0; i < (1 << maxn); i++)
			seg[i] = mx[i] = lazy[i] = 0;
	}
	void build (int i){
		if ((i << 1) >= (1 << maxn)) return;
		build(i << 1), build((i << 1) ^ 1);
		mx[i] = max(mx[i << 1], mx[(i << 1) ^ 1]);
	}
	void shift (int i){
		if ((i << 1) >= (1 << maxn)) return;
		lazy[i << 1] = max(lazy[i << 1], lazy[i]);
		lazy[(i << 1) ^ 1] = max(lazy[(i << 1) ^ 1], lazy[i]);
		seg[i << 1] = max(seg[i << 1], mx[i << 1] + lazy[i << 1]);
		seg[(i << 1) ^ 1] = max(seg[(i << 1) ^ 1], mx[(i << 1) ^ 1] + lazy[(i << 1) ^ 1]);
		lazy[i] = 0;
	}
	void update (int i, int L, int R, int l, int r, int x){
		if (L > r || R < l) return;
		if (L >= l && R <= r){
			lazy[i] = max(lazy[i], x);
			seg[i] = max(seg[i], mx[i] + lazy[i]);
			return;
		}
		shift(i);
		int mid = (R + L) >> 1;
		update(i << 1, L, mid, l, r, x);
		update((i << 1) ^ 1, mid + 1, R, l, r, x);
		seg[i] = max(seg[i << 1], seg[(i << 1) ^ 1]);
	}
	int get (int i, int L, int R, int l, int r){
		if (L > r || R < l) return 0;
		if (L >= l && R <= r) return seg[i];
		shift(i);
		int mid = (R + L) >> 1;
		return max(get(i << 1, L, mid, l, r), get((i << 1) ^ 1, mid + 1, R, l, r));
	}
};

segment seg;

int n, q;

int32_t main (){
	ios_base::sync_with_stdio(0);
	cin >> n;
	vector <int> a(n), p[2 * n];
	vector <pair <int, int>> que[n];
	for (int i = 0; i < n; i++)
		cin >> a[i], seg.mx[kaf + i] = a[i];
	seg.build(1);
	cin >> q;
	vector <int> ans(q);
	for (int l, r, i = 0; i < q; i++)
		cin >> l >> r,
		que[--l].push_back({--r, i});
	stack <int> stc;
	for (int i = 0; i < n; i++){
		while (stc.size() && a[i] > a[stc.top()])
			p[stc.top()].push_back(i),
			stc.pop();
		if (stc.size()) p[stc.top()].push_back(i);
		stc.push(i);
	}
	for (int i = n - 1; ~i; i--){
		for (auto r : p[i])
			if (2 * r - i < n)
				seg.update(1, 0, kaf - 1, 2 * r - i, n - 1, a[i] + a[r]);
		for (auto [r, ind] : que[i])
			ans[ind] = seg.get(1, 0, kaf - 1, i, r);
	}
	for (int i : ans) cout << i << '\n';
}

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