Submission #943545

#	Time	Username	Problem	Language	Result	Execution time	Memory
943545		PlayVoltz	Triple Jump (JOI19_jumps)	C++17	0 / 100	164 ms	53160 KiB

jumps

#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

vector<int> vect;

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 = vect[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 up(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->up(l, r, v);
		right->up(l, r, v);
		r_val = max(left->r_val, right->r_val);
	}
	int query(int l, int r) {
		if (l > E || r < S) {
			return -(int)1e9;
		}
		if (l <= S && E <= r) {
			return r_val;
		}
		prop();
		return max(left->query(l, r), right->query(l, r));
	}
} *st;

int32_t main(){
	int n, q, a, b;
	cin>>n;
	vect.resize(n+1);
	vector<vector<pii> > queries(n+1);
	for (int i=1; i<=n; ++i)cin>>vect[i];
	cin>>q;
	vector<int> ans(q);
	vector<vector<int> > next(n+1);
	st = new node(1, n);
	for (int i=0; i<q; ++i){
		cin>>a>>b;
		queries[a].pb(mp(b, i));
	}
	stack<int> s;
	for (int i=1; i<=n; ++i){
		while (!s.empty()&&vect[s.top()]<vect[i])next[s.top()].pb(i), s.pop();
		s.push(i);
	}
	while (!s.empty())s.pop();
	for (int i=n; i>=1; --i){
		while (!s.empty()&&vect[s.top()]<vect[i])next[i].pb(s.top()), s.pop();
		s.push(i);
	}
	for (int i=n; i>=1; --i){
		for (auto c:next[i])st->up(2*c-i, n, vect[i]+vect[c]);
		for (auto c:queries[i])ans[c.se]=st->query(i, c.fi);
	}
	for (auto a:ans)cout<<a<<"\n";
}

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