oj.uz

Submission #160356

# Submission time Handle Problem Language Result Execution time Memory
160356 2019-10-27T06:31:18 Z iefnah06 Triple Jump (JOI19_jumps) C++11
100 / 100
 1282 ms 107512 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24312 KB Output is correct
2 Correct 25 ms 24312 KB Output is correct
3 Correct 25 ms 24332 KB Output is correct
4 Correct 25 ms 24312 KB Output is correct
5 Correct 24 ms 24312 KB Output is correct
6 Correct 25 ms 24268 KB Output is correct
7 Correct 24 ms 24312 KB Output is correct
8 Correct 26 ms 24312 KB Output is correct
9 Correct 27 ms 24316 KB Output is correct
10 Correct 24 ms 24284 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24312 KB Output is correct
2 Correct 25 ms 24312 KB Output is correct
3 Correct 25 ms 24332 KB Output is correct
4 Correct 25 ms 24312 KB Output is correct
5 Correct 24 ms 24312 KB Output is correct
6 Correct 25 ms 24268 KB Output is correct
7 Correct 24 ms 24312 KB Output is correct
8 Correct 26 ms 24312 KB Output is correct
9 Correct 27 ms 24316 KB Output is correct
10 Correct 24 ms 24284 KB Output is correct
11 Correct 356 ms 42904 KB Output is correct
12 Correct 340 ms 42744 KB Output is correct
13 Correct 360 ms 42872 KB Output is correct
14 Correct 362 ms 42904 KB Output is correct
15 Correct 396 ms 42988 KB Output is correct
16 Correct 375 ms 42232 KB Output is correct
17 Correct 357 ms 42272 KB Output is correct
18 Correct 324 ms 42104 KB Output is correct
19 Correct 361 ms 42744 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 45920 KB Output is correct
2 Correct 120 ms 45560 KB Output is correct
3 Correct 124 ms 46444 KB Output is correct
4 Correct 172 ms 45816 KB Output is correct
5 Correct 180 ms 45816 KB Output is correct
6 Correct 168 ms 45244 KB Output is correct
7 Correct 165 ms 45176 KB Output is correct
8 Correct 168 ms 45048 KB Output is correct
9 Correct 169 ms 45432 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24312 KB Output is correct
2 Correct 25 ms 24312 KB Output is correct
3 Correct 25 ms 24332 KB Output is correct
4 Correct 25 ms 24312 KB Output is correct
5 Correct 24 ms 24312 KB Output is correct
6 Correct 25 ms 24268 KB Output is correct
7 Correct 24 ms 24312 KB Output is correct
8 Correct 26 ms 24312 KB Output is correct
9 Correct 27 ms 24316 KB Output is correct
10 Correct 24 ms 24284 KB Output is correct
11 Correct 356 ms 42904 KB Output is correct
12 Correct 340 ms 42744 KB Output is correct
13 Correct 360 ms 42872 KB Output is correct
14 Correct 362 ms 42904 KB Output is correct
15 Correct 396 ms 42988 KB Output is correct
16 Correct 375 ms 42232 KB Output is correct
17 Correct 357 ms 42272 KB Output is correct
18 Correct 324 ms 42104 KB Output is correct
19 Correct 361 ms 42744 KB Output is correct
20 Correct 182 ms 45920 KB Output is correct
21 Correct 120 ms 45560 KB Output is correct
22 Correct 124 ms 46444 KB Output is correct
23 Correct 172 ms 45816 KB Output is correct
24 Correct 180 ms 45816 KB Output is correct
25 Correct 168 ms 45244 KB Output is correct
26 Correct 165 ms 45176 KB Output is correct
27 Correct 168 ms 45048 KB Output is correct
28 Correct 169 ms 45432 KB Output is correct
29 Correct 1252 ms 101752 KB Output is correct
30 Correct 1146 ms 100984 KB Output is correct
31 Correct 1101 ms 103212 KB Output is correct
32 Correct 1236 ms 101688 KB Output is correct
33 Correct 1270 ms 101688 KB Output is correct
34 Correct 1236 ms 99448 KB Output is correct
35 Correct 1257 ms 99244 KB Output is correct
36 Correct 1259 ms 99160 KB Output is correct
37 Correct 1252 ms 100604 KB Output is correct
38 Correct 754 ms 107316 KB Output is correct
39 Correct 931 ms 107512 KB Output is correct
40 Correct 789 ms 104044 KB Output is correct
41 Correct 731 ms 103536 KB Output is correct
42 Correct 747 ms 103512 KB Output is correct
43 Correct 738 ms 105336 KB Output is correct
44 Correct 843 ms 106860 KB Output is correct
45 Correct 833 ms 106872 KB Output is correct
46 Correct 832 ms 103580 KB Output is correct
47 Correct 825 ms 103332 KB Output is correct
48 Correct 835 ms 103312 KB Output is correct
49 Correct 814 ms 105508 KB Output is correct
50 Correct 1282 ms 104952 KB Output is correct
51 Correct 1002 ms 104952 KB Output is correct
52 Correct 939 ms 102420 KB Output is correct
53 Correct 934 ms 102224 KB Output is correct
54 Correct 943 ms 102080 KB Output is correct
55 Correct 1216 ms 103812 KB Output is correct