oj.uz

Submission #162034

# Submission time Handle Problem Language Result Execution time Memory
162034 2019-11-06T03:09:06 Z Anai Triple Jump (JOI19_jumps) C++14
0 / 100
 103 ms 11088 KB 
#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], nxt[N], ant[N];
Nod pom[N * 4];

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


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

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

	for (int i = 1; i < n; ++i)
		if (nxt[i] == -1)
			nxt[i] = i + 1; }

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 = pom[nod].maxval + qval;
		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) {
		if (pom[nod].enforce)
			pom[nod].enforce = max(pom[nod].enforce, qval);
		else {
			pom[nod].enforce = qval;
			pom[nod].maxans = max(pom[nod].maxans, pom[nod].maxval + qval); }
		return; }
	prop(nod);
	int mid = (st + dr) / 2;
	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) {
	if (nxt[pos] == -1)
		return;

	qval = v[pos] + v[nxt[pos]];
	ql = 2 * nxt[pos] - 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; }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Incorrect 4 ms 2296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Incorrect 4 ms 2296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 11088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Incorrect 4 ms 2296 KB Output isn't correct
3 Halted 0 ms 0 KB -