Submission #797290

#	Time	Username	Problem	Language	Result	Execution time	Memory
797290		ymm	Triple Jump (JOI19_jumps)	C++17	100 / 100	868 ms	79304 KiB

jumps

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 500'010;

namespace seg {
	struct node {
		int ans, mxab, mxc;
	} t[N*4];
	int sz;

	node merge(const node &l, const node &r) {
		node ans;
		ans.ans = max({l.ans, r.ans, l.mxab + r.mxc});
		ans.mxab = max(l.mxab, r.mxab);
		ans.mxc = max(l.mxc, r.mxc);
		return ans;
	}
	void merge(int i) { t[i] = merge(t[2*i+1], t[2*i+2]); }

	void init(const vector<int> &vec, int i, int b, int e) {
		if (e-b == 1) {
			t[i].ans = t[i].mxc = vec[b];
			t[i].mxab = 0;
			return;
		}
		init(vec, 2*i+1, b, (b+e)/2);
		init(vec, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void init(const vector<int> &vec) {
		sz = vec.size();
		init(vec, 0, 0, sz);
	}

	void up(int p, int x, int i, int b, int e) {
		if (e-b == 1) {
			t[i].mxab = max(t[i].mxab, x);
			t[i].ans = t[i].mxab + t[i].mxc;
			return;
		}
		if (p < (b+e)/2)
			up(p, x, 2*i+1, b, (b+e)/2);
		else
			up(p, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void up(int p, int x) { up(p, x, 0, 0, sz); }

	node get(int l, int r, int i, int b, int e) {
		if (l <= b && e <= r)
			return t[i];
		if (l < (b+e)/2 && (b+e)/2 < r) {
			return merge(get(l, r, 2*i+1, b, (b+e)/2),
			             get(l, r, 2*i+2, (b+e)/2, e));
		}
		if (l < (b+e)/2)
			return get(l, r, 2*i+1, b, (b+e)/2);
		else
			return get(l, r, 2*i+2, (b+e)/2, e);
	}
	int get(int l, int r) { return get(l, r, 0, 0, sz).ans; }
}

vector<pii> ab[N];
vector<pii> Q[N];
int ans[N];
int a[N];
int n, q;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n)
		cin >> a[i];
	cin >> q;
	Loop (i,0,q) {
		int l, r;
		cin >> l >> r;
		--l;
		Q[l].push_back({i,r});
	}
	vector<int> st;
	Loop (i,0,n) {
		while (st.size() && a[st.back()] < a[i])
			st.pop_back();
		if (st.size())
			ab[st.back()].push_back({a[i] + a[st.back()], 2*i - st.back()});
		st.push_back(i);
	}
	st.clear();
	LoopR (i,0,n) {
		while (st.size() && a[st.back()] <= a[i])
			st.pop_back();
		if (st.size())
			ab[i].push_back({a[i] + a[st.back()], 2*st.back()-i});
		st.push_back(i);
	}
	seg::init(vector<int>(a, a+n));
	LoopR (i,0,n) {
		for (auto [sum, pos] : ab[i]) {
			if (pos >= n)
				continue;
			seg::up(pos, sum);
		}
		for (auto [q, r] : Q[i])
			ans[q] = seg::get(i, r);
	}
	Loop (i,0,q)
		cout << ans[i] << '\n';
}

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