Submission #1291470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291470		Jawad_Akbar_JJ	Triple Jump (JOI19_jumps)	C++20	100 / 100	801 ms	56276 KiB

jumps

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

using namespace std;
const int N = (1<<19) + 1;
int Mx1[N<<1], Mx2[N<<1], Mx3[N<<1], Arr[N], Ans[N];
vector<pair<int,int>> vec[N], rng;

void build(int cur = 1, int st = 1, int en = N){
	if (en - st == 1){
		Mx1[cur] = Arr[st];
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	build(lc, st, mid);
	build(rc, mid, en);
	Mx1[cur] = max(Mx1[lc], Mx1[rc]);
}

void Push(int cur, int lc, int rc){
	Mx2[lc] = max(Mx2[lc], Mx2[cur]), Mx3[lc] = max(Mx3[lc], Mx2[lc] + Mx1[lc]);
	Mx2[rc] = max(Mx2[rc], Mx2[cur]), Mx3[rc] = max(Mx3[rc], Mx2[rc] + Mx1[rc]);
}

void insert(int l, int r, int vl, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return;
	if (l <= st and r >= en){
		Mx2[cur] = max(Mx2[cur], vl);
		Mx3[cur] = max(Mx3[cur], Mx2[cur] + Mx1[cur]);
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Push(cur, lc, rc);

	insert(l, r, vl, lc, st, mid);
	insert(l, r, vl, rc, mid, en); 
	Mx3[cur] = max(Mx3[lc], Mx3[rc]);
}

int get(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return Mx3[cur];
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Push(cur, lc, rc);

	return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, q;
	cin>>n;

	vector<int> vc, Vc;
	for (int i=1;i<=n;i++){
		cin>>Arr[i];

		while (vc.size() > 0 and Arr[vc.back()] <= Arr[i])
			rng.push_back({vc.back(), i}), vc.pop_back();
		vc.push_back(i);
	}

	for (int i=n;i>=1;i--){
		while (Vc.size() > 0 and Arr[Vc.back()] <= Arr[i])
			rng.push_back({i, Vc.back()}), Vc.pop_back();
		Vc.push_back(i);
	}
	sort(rng.begin(), rng.end());

	build();

	cin>>q;
	for (int i=1;i<=q;i++){
		int l, r;
		cin>>l>>r;
		vec[l].push_back({r, i});
	}

	for (int i=n;i>=1;i--){
		while (rng.size() > 0 and rng.back().first >= i){
			auto [a, b] = rng.back();
			rng.pop_back();
			insert(2 * b - a, N, Arr[a] + Arr[b]);
		}
		for (auto [r, id] : vec[i])
			Ans[id] = get(i + 2, r + 1);
	}

	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