Submission #162364

#	Time	Username	Problem	Language	Result	Execution time	Memory
162364		Anai	Triple Jump (JOI19_jumps)	C++14	100 / 100	1315 ms	68004 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

struct Query {
	int l, r, idx; };

struct Nod {
	int maxval, maxans, enforce; };

int v[N], ant[N];
vector<int> nxt[N];
Nod pom[N * 4];

vector<Query> qs;
int n, q, ql, qr, qval;

static void get_nxt() {
	vector<int> stk;

	for (int i = 1; i <= n; ++i) {
		while (!stk.empty() && v[stk.back()] <= v[i]) {
			nxt[stk.back()].push_back(i);
			stk.pop_back(); }
		if (!stk.empty())
			nxt[stk.back()].push_back(i);
		stk.push_back(i); } 

	for (int i = 0; i + 1 < stk.size(); ++i) {
		for (int j = stk[i] + 1; j <= stk[i + 1]; ++j)
	 		nxt[stk[i]].push_back(j); } }

static void prop(int nod) { 
	if (pom[nod].enforce == 0)
		return;
	else {
		pom[2 * nod + 1].enforce = max(pom[2 * nod + 1].enforce, pom[nod].enforce);
		pom[2 * nod].enforce = max(pom[2 * nod].enforce, pom[nod].enforce);
		pom[nod].maxans = max(pom[nod].maxans, pom[nod].maxval + pom[nod].enforce);
		pom[nod].enforce = 0; } }

static int eval(Nod nod) {
	return max(nod.maxans, nod.maxval + nod.enforce); }

static Nod join(Nod a, Nod b) {
	return (Nod {max(a.maxval, b.maxval), max(eval(a), eval(b)), 0}); }

static void build(int nod, int st, int dr) {
	if (st == dr) {
		pom[nod] = {v[st], v[dr], 0}; // OCD right here
		return; }
	int mid = (st + dr) / 2;
	build(2 * nod, st, mid);
	build(2 * nod + 1, mid + 1, dr);
	pom[nod] = join(pom[2 * nod], pom[2 * nod + 1]); }

static void update(int nod, int st, int dr) {
	if (ql <= st && dr <= qr) {
		pom[nod].enforce = max(pom[nod].enforce, qval);
		pom[nod].maxans = max(pom[nod].maxans, pom[nod].maxval + pom[nod].enforce);
		return; }
	int mid = (st + dr) / 2;

	prop(nod);
	if (ql <= mid)
		update(2 * nod, st, mid);
	if (mid < qr)
		update(2 * nod + 1, mid + 1, dr);

	pom[nod] = join(pom[2 * nod], pom[2 * nod + 1]); }

static int query(int nod, int st, int dr) {
	if (ql <= st && dr <= qr)
		return eval(pom[nod]);

	int ans = 0, mid = (st + dr) / 2;
	prop(nod);
	if (ql <= mid)
		ans = max(ans, query(2 * nod, st, mid));
	if (mid < qr)
		ans = max(ans, query(2 * nod + 1, mid + 1, dr));
	return ans; }

static void baga(int pos) {
	for (auto nex: nxt[pos]) {
		qval = v[pos] + v[nex];
		ql = 2 * nex - pos;
		qr = n;
		if (ql <= qr)
			update(1, 1, n); } }


int main() {
#ifdef HOME
	freopen("triple_jump.in", "r", stdin);
	freopen("triple_jump.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int ptr;

	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> v[i];

	cin >> q;
	qs.resize(q);
	for (int i = 0; i < q; ++i) {
		cin >> qs[i].l >> qs[i].r;
		qs[i].idx = i; }

	sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return a.l > b.l; });
	build(1, 1, n);
	get_nxt();

	ptr = n;
	for (auto myq: qs) {
		while (myq.l <= ptr)
			baga(ptr--);
		ql = myq.l + 2, qr = myq.r;
		ant[myq.idx] = query(1, 1, n); }

	for (int i = 0; i < q; ++i)
		cout << ant[i] << '\n';

	return 0; }

Compilation message (stderr)

jumps.cpp: In function 'void get_nxt()':
jumps.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < stk.size(); ++i) {
                  ~~~~~~^~~~~~~~~~~~

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