oj.uz

Submission #797163

# Submission time Handle Problem Language Result Execution time Memory
797163 2023-07-29T07:31:33 Z Sohsoh84 Triple Jump (JOI19_jumps) C++17
100 / 100
 1008 ms 130588 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define int			ll
#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 5e5 + 10;
const ll INF = 8e18;

int FL[MAXN], FR[MAXN], A[MAXN], n, q, ans[MAXN];
vector<int> L_vec[MAXN];
vector<pll> QL[MAXN];

namespace segment {
	ll lz[MAXN << 2], sg[MAXN << 2], mn_tof[MAXN << 2], mx_tof[MAXN << 2];
	
	void build(int l = 1, int r = n, int v = 1) {
		if (l == r) sg[v] = A[l];
		else {
			int mid = (l + r) >> 1;
			build(l, mid, v << 1);
			build(mid + 1, r, v << 1 | 1);
			sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
		}
	}

	inline void push(int v) { // be sure that tof[v] != -1
		if (lz[v] == 0) return;
		sg[v] += lz[v] - mx_tof[v];
		mn_tof[v] = lz[v];
		mx_tof[v] = lz[v];

		if ((v << 1 | 1) < (MAXN << 2)) {
			lz[v << 1] = max(lz[v << 1], lz[v]);
			lz[v << 1 | 1] = max(lz[v << 1 | 1], lz[v]);
		}

		lz[v] = 0;
	}

	void update(int ql, int qr, ll val, int l = 1, int r = n, int v = 1) {
		push(v);
		if (ql > r || qr < l || val <= mn_tof[v]) return;
		if (ql <= l && qr >= r && mx_tof[v] == mn_tof[v]) {
			lz[v] = val;
			push(v);
			return;
		}

		int mid = (l + r) >> 1;
		update(ql, qr, val, l, mid, v << 1);
		update(ql, qr, val, mid + 1, r, v << 1 | 1);

		sg[v] = max(sg[v << 1], sg[v << 1 | 1]);	
		mn_tof[v] = min(mn_tof[v << 1], mn_tof[v << 1 | 1]);
		mx_tof[v] = max(mx_tof[v << 1], mx_tof[v << 1 | 1]);
	}

	ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
		push(v);
		if (ql > r || qr < l) return -INF;
		if (ql <= l && qr >= r) return sg[v];

		int mid = (l + r) >> 1;
		return max(query(ql, qr, l, mid, v << 1),
				query(ql, qr, mid + 1, r, v << 1 | 1));
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> A[i];
	
	for (int i = 1; i <= n; i++)
		for (FL[i] = i - 1; FL[i] && A[FL[i]] < A[i]; FL[i] = FL[FL[i]]);

	for (int i = n; i > 0; i--)
		for (FR[i] = i + 1; FR[i] <= n && A[FR[i]] < A[i]; FR[i] = FR[FR[i]]);

	for (int i = 1; i <= n; i++) {
		if (FL[i] > 0) L_vec[FL[i]].push_back(i);
		if (FR[i] <= n) L_vec[i].push_back(FR[i]);
	}

	segment::build();
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		QL[l].push_back({i, r});
	}

	for (int l = n; l > 0; l--) {
		for (int mid : L_vec[l]) {
			int val = A[l] + A[mid];
			int r = mid + mid - l;
			if (r <= n) segment::update(r, n, val);
		}

		for (auto [q, r] : QL[l])
			ans[q] = segment::query(l + 2, r);
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct
3 Correct 11 ms 23852 KB Output is correct
4 Correct 11 ms 23852 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23888 KB Output is correct
9 Correct 12 ms 23840 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct
3 Correct 11 ms 23852 KB Output is correct
4 Correct 11 ms 23852 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23888 KB Output is correct
9 Correct 12 ms 23840 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 216 ms 47088 KB Output is correct
12 Correct 221 ms 46940 KB Output is correct
13 Correct 225 ms 47056 KB Output is correct
14 Correct 211 ms 47036 KB Output is correct
15 Correct 218 ms 47168 KB Output is correct
16 Correct 220 ms 46504 KB Output is correct
17 Correct 234 ms 46576 KB Output is correct
18 Correct 221 ms 46304 KB Output is correct
19 Correct 226 ms 47004 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 56464 KB Output is correct
2 Correct 90 ms 54196 KB Output is correct
3 Correct 91 ms 55288 KB Output is correct
4 Correct 160 ms 56560 KB Output is correct
5 Correct 168 ms 56516 KB Output is correct
6 Correct 149 ms 56492 KB Output is correct
7 Correct 148 ms 56476 KB Output is correct
8 Correct 154 ms 56480 KB Output is correct
9 Correct 152 ms 56512 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct
3 Correct 11 ms 23852 KB Output is correct
4 Correct 11 ms 23852 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23888 KB Output is correct
9 Correct 12 ms 23840 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 216 ms 47088 KB Output is correct
12 Correct 221 ms 46940 KB Output is correct
13 Correct 225 ms 47056 KB Output is correct
14 Correct 211 ms 47036 KB Output is correct
15 Correct 218 ms 47168 KB Output is correct
16 Correct 220 ms 46504 KB Output is correct
17 Correct 234 ms 46576 KB Output is correct
18 Correct 221 ms 46304 KB Output is correct
19 Correct 226 ms 47004 KB Output is correct
20 Correct 154 ms 56464 KB Output is correct
21 Correct 90 ms 54196 KB Output is correct
22 Correct 91 ms 55288 KB Output is correct
23 Correct 160 ms 56560 KB Output is correct
24 Correct 168 ms 56516 KB Output is correct
25 Correct 149 ms 56492 KB Output is correct
26 Correct 148 ms 56476 KB Output is correct
27 Correct 154 ms 56480 KB Output is correct
28 Correct 152 ms 56512 KB Output is correct
29 Correct 938 ms 116584 KB Output is correct
30 Correct 653 ms 111372 KB Output is correct
31 Correct 794 ms 113524 KB Output is correct
32 Correct 893 ms 116552 KB Output is correct
33 Correct 923 ms 116476 KB Output is correct
34 Correct 904 ms 116588 KB Output is correct
35 Correct 964 ms 124900 KB Output is correct
36 Correct 1008 ms 124980 KB Output is correct
37 Correct 938 ms 126300 KB Output is correct
38 Correct 676 ms 130084 KB Output is correct
39 Correct 721 ms 130116 KB Output is correct
40 Correct 659 ms 126796 KB Output is correct
41 Correct 638 ms 126288 KB Output is correct
42 Correct 610 ms 126216 KB Output is correct
43 Correct 686 ms 128036 KB Output is correct
44 Correct 669 ms 130440 KB Output is correct
45 Correct 786 ms 130432 KB Output is correct
46 Correct 672 ms 127216 KB Output is correct
47 Correct 641 ms 126880 KB Output is correct
48 Correct 682 ms 126852 KB Output is correct
49 Correct 661 ms 128804 KB Output is correct
50 Correct 727 ms 130584 KB Output is correct
51 Correct 769 ms 130588 KB Output is correct
52 Correct 721 ms 128172 KB Output is correct
53 Correct 711 ms 127828 KB Output is correct
54 Correct 745 ms 127768 KB Output is correct
55 Correct 726 ms 129508 KB Output is correct