Submission #299654

#	Time	Username	Problem	Language	Result	Execution time	Memory
299654		pit4h	Triple Jump (JOI19_jumps)	C++14	100 / 100	1742 ms	90452 KiB

jumps

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

const int N = 5e5+1;
int n, q, ans[N];
vector<pii> queries[N], vec[N];
struct Segtree {
	vector<int> node, push, max_in_range;
	int base;
	void init(int sz, vector<int> leaves) {
		base = 1;
		while(base < sz) base *= 2;
		node.resize(2*base+1);
		push.resize(2*base+1);
		max_in_range.resize(2*base+1);
		for(int i=0; i<(int)leaves.size(); ++i) {
			max_in_range[i+base] = leaves[i];
		}
		for(int i=base-1; i>=1; --i) {
			max_in_range[i] = max(max_in_range[i*2], max_in_range[i*2+1]);
		}
	}
	void Push(int x, int y) {
		node[y] = max(node[y], push[x] + max_in_range[y]);
		push[y] = max(push[y], push[x]);
	}
	void ins(int l, int r, int val, int id, int L, int R) {
		if(l > R || r < L) return;
		if(L>=l && R<=r) {
			node[id] = max(node[id], val + max_in_range[id]);
			push[id] = max(push[id], val);
			return;
		}
		int M = (L+R)/2;
		Push(id, id*2); Push(id, id*2+1);
		ins(l, r, val, id*2, L, M);
		ins(l, r, val, id*2+1, M+1, R);
		node[id] = max(node[id*2], node[id*2+1]);
	}
	int qry(int l, int r, int id, int L, int R) {
		if(l > R || r < L) return 0;
		if(L>=l && R<=r) {
			return node[id];
		}
		int M = (L+R)/2;
		Push(id, id*2); Push(id, id*2+1);
		int res = max(qry(l, r, id*2, L, M), qry(l, r, id*2+1, M+1, R));
		node[id] = max(node[id*2], node[id*2+1]);
		return res;
	}	
};
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	vector<int> a(n);
	for(int i=0; i<n; ++i) {
		cin>>a[i];
	}
	Segtree tree;
	tree.init(n, a);
	cin>>q;
	for(int i=0; i<q; ++i) {
		int l, r; cin>>l>>r;
		queries[l-1].push_back(mp(r-1, i));
	}
	vector<int> mono;
	for(int i=0; i<n; ++i) {
		while(mono.size() && a[mono.back()] <= a[i]) {
			vec[mono.back()].push_back(mp(a[i] + a[mono.back()], i+(i-mono.back())));	
			mono.pop_back();
		}
		if(mono.size()) {
			vec[mono.back()].push_back(mp(a[i] + a[mono.back()], i+(i-mono.back())));
		}
		mono.push_back(i);
	}
	for(int i=n-1; i>=0; --i) {
		for(auto j: vec[i]) {
			if(j.nd > n-1) continue;
			tree.ins(j.nd, n-1, j.st, 1, 0, tree.base-1);
		}
		for(auto j: queries[i]) {
			ans[j.nd] = tree.qry(i, j.st, 1, 0, tree.base-1);
		}
	}
	for(int i=0; i<q; ++i) {
		cout<<ans[i]<<'\n';
	}
}

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