제출 #160356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160356		iefnah06	3단 점프 (JOI19_jumps)	C++11	100 / 100	1282 ms	107512 KiB

jumps

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

const int INF = 1e9;

const int MAXN = 5.1e5;
int N;
int A[MAXN];

struct node_t {
	int base;
	int add;
	int best;

	node_t() {}
	node_t(int base_, int add_, int best_) : base(base_), add(add_), best(best_) {}

	node_t operator + (const node_t& o) const {
		node_t res;
		res.base = max(base, o.base);
		res.add = max(add, o.add);
		res.best = max({best, o.best, add + o.base});
		return res;
	}
};

struct seg {
	seg* ch[2];
	node_t res;

	seg() {}

	void update() {
		assert(ch[0]);
		res = ch[0]->res + ch[1]->res;
	}
};
seg nodes[MAXN*2];
int NODE;
seg* ROOT;

seg* build(int x = 0, int y = N) {
	seg* r = &nodes[NODE++];
	if (y - x == 1) {
		r->res = node_t(A[x], -INF, -INF);
	} else {
		int z = (x + y) / 2;
		r->ch[0] = build(x, z);
		r->ch[1] = build(z, y);
		r->update();
	}
	return r;
}

void update(int k, int v, int x = 0, int y = N, seg* n = ROOT) {
	if (y - x == 1) {
		n->res.add = max(n->res.add, v);
		n->res.best = n->res.base + n->res.add;
	} else {
		int z = (x + y) / 2;
		if (k < z) {
			update(k, v, x, z, n->ch[0]);
		} else {
			update(k, v, z, y, n->ch[1]);
		}
		n->update();
	}
}

node_t query(int l, int r, int x = 0, int y = N, seg* n = ROOT) {
	if (l <= x && y <= r) {
		return n->res;
	} else {
		int z = (x + y) / 2;
		if (r <= z) {
			return query(l, r, x, z, n->ch[0]);
		} else if (z <= l) {
			return query(l, r, z, y, n->ch[1]);
		} else {
			return query(l, r, x, z, n->ch[0]) + query(l, r, z, y, n->ch[1]);
		}
	}
}

vector<int> candidates[MAXN];
vector<array<int, 2>> queries[MAXN];

const int MAXQ = 5.1e5;
int ans[MAXQ];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	vector<int> st;
	for (int i = 0; i < N; i++) {
		while (!st.empty() && A[st.back()] <= A[i]) {
			candidates[st.back()].push_back(i);
			st.pop_back();
		}
		if (!st.empty()) {
			candidates[st.back()].push_back(i);
		}
		st.push_back(i);
	}

	int Q; cin >> Q;
	for (int q = 0; q < Q; q++) {
		int l, r; cin >> l >> r; l--;
		queries[l].push_back({r, q});
	}

	ROOT = build();
	for (int l = N-1; l >= 0; l--) {
		for (int r : candidates[l]) {
			int x = 2 * r - l;
			if (x < N) {
				update(x, A[l] + A[r]);
			}
		}
		for (auto q : queries[l]) {
			ans[q[1]] = query(l, q[0]).best;
		}
	}

	for (int q = 0; q < Q; q++) {
		cout << ans[q] << '\n'; 
	}

	return 0;
}

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