oj.uz

Submission #1116243

# Submission time Handle Problem Language Result Execution time Memory
1116243 2024-11-21T11:29:49 Z sinatbtfard Triple Jump (JOI19_jumps) C++17
100 / 100
 1095 ms 142912 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 21, kaf = 1 << 20, inf = 1e15;

struct segment {
	int seg[1 << maxn], mx[1 << maxn], lazy[1 << maxn];
	segment (){
		for (int i = 0; i < (1 << maxn); i++)
			seg[i] = mx[i] = lazy[i] = 0;
	}
	void build (int i){
		if ((i << 1) >= (1 << maxn)) return;
		build(i << 1), build((i << 1) ^ 1);
		mx[i] = max(mx[i << 1], mx[(i << 1) ^ 1]);
	}
	void shift (int i){
		if ((i << 1) >= (1 << maxn)) return;
		lazy[i << 1] = max(lazy[i << 1], lazy[i]);
		lazy[(i << 1) ^ 1] = max(lazy[(i << 1) ^ 1], lazy[i]);
		seg[i << 1] = max(seg[i << 1], mx[i << 1] + lazy[i << 1]);
		seg[(i << 1) ^ 1] = max(seg[(i << 1) ^ 1], mx[(i << 1) ^ 1] + lazy[(i << 1) ^ 1]);
		lazy[i] = 0;
	}
	void update (int i, int L, int R, int l, int r, int x){
		if (L > r || R < l) return;
		if (L >= l && R <= r){
			lazy[i] = max(lazy[i], x);
			seg[i] = max(seg[i], mx[i] + lazy[i]);
			return;
		}
		shift(i);
		int mid = (R + L) >> 1;
		update(i << 1, L, mid, l, r, x);
		update((i << 1) ^ 1, mid + 1, R, l, r, x);
		seg[i] = max(seg[i << 1], seg[(i << 1) ^ 1]);
	}
	int get (int i, int L, int R, int l, int r){
		if (L > r || R < l) return 0;
		if (L >= l && R <= r) return seg[i];
		shift(i);
		int mid = (R + L) >> 1;
		return max(get(i << 1, L, mid, l, r), get((i << 1) ^ 1, mid + 1, R, l, r));
	}
};

segment seg;

int n, q;

int32_t main (){
	ios_base::sync_with_stdio(0);
	cin >> n;
	vector <int> a(n), p[2 * n];
	vector <pair <int, int>> que[n];
	for (int i = 0; i < n; i++)
		cin >> a[i], seg.mx[kaf + i] = a[i];
	seg.build(1);
	cin >> q;
	vector <int> ans(q);
	for (int l, r, i = 0; i < q; i++)
		cin >> l >> r,
		que[--l].push_back({--r, i});
	stack <int> stc;
	for (int i = 0; i < n; i++){
		while (stc.size() && a[i] > a[stc.top()])
			p[stc.top()].push_back(i),
			stc.pop();
		if (stc.size()) p[stc.top()].push_back(i);
		stc.push(i);
	}
	for (int i = n - 1; ~i; i--){
		for (auto r : p[i])
			if (2 * r - i < n)
				seg.update(1, 0, kaf - 1, 2 * r - i, n - 1, a[i] + a[r]);
		for (auto [r, ind] : que[i])
			ans[ind] = seg.get(1, 0, kaf - 1, i, r);
	}
	for (int i : ans) cout << i << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 49488 KB Output is correct
2 Correct 11 ms 49700 KB Output is correct
3 Correct 11 ms 49488 KB Output is correct
4 Correct 11 ms 49740 KB Output is correct
5 Correct 11 ms 49488 KB Output is correct
6 Correct 12 ms 49488 KB Output is correct
7 Correct 12 ms 49712 KB Output is correct
8 Correct 11 ms 49488 KB Output is correct
9 Correct 11 ms 49716 KB Output is correct
10 Correct 12 ms 49488 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 49488 KB Output is correct
2 Correct 11 ms 49700 KB Output is correct
3 Correct 11 ms 49488 KB Output is correct
4 Correct 11 ms 49740 KB Output is correct
5 Correct 11 ms 49488 KB Output is correct
6 Correct 12 ms 49488 KB Output is correct
7 Correct 12 ms 49712 KB Output is correct
8 Correct 11 ms 49488 KB Output is correct
9 Correct 11 ms 49716 KB Output is correct
10 Correct 12 ms 49488 KB Output is correct
11 Correct 284 ms 77116 KB Output is correct
12 Correct 310 ms 76984 KB Output is correct
13 Correct 267 ms 77128 KB Output is correct
14 Correct 291 ms 76872 KB Output is correct
15 Correct 283 ms 77016 KB Output is correct
16 Correct 275 ms 76492 KB Output is correct
17 Correct 291 ms 76360 KB Output is correct
18 Correct 284 ms 76368 KB Output is correct
19 Correct 277 ms 77000 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 72776 KB Output is correct
2 Correct 120 ms 73288 KB Output is correct
3 Correct 124 ms 74836 KB Output is correct
4 Correct 212 ms 74568 KB Output is correct
5 Correct 225 ms 74548 KB Output is correct
6 Correct 206 ms 73800 KB Output is correct
7 Correct 190 ms 73752 KB Output is correct
8 Correct 197 ms 73660 KB Output is correct
9 Correct 207 ms 74080 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 49488 KB Output is correct
2 Correct 11 ms 49700 KB Output is correct
3 Correct 11 ms 49488 KB Output is correct
4 Correct 11 ms 49740 KB Output is correct
5 Correct 11 ms 49488 KB Output is correct
6 Correct 12 ms 49488 KB Output is correct
7 Correct 12 ms 49712 KB Output is correct
8 Correct 11 ms 49488 KB Output is correct
9 Correct 11 ms 49716 KB Output is correct
10 Correct 12 ms 49488 KB Output is correct
11 Correct 284 ms 77116 KB Output is correct
12 Correct 310 ms 76984 KB Output is correct
13 Correct 267 ms 77128 KB Output is correct
14 Correct 291 ms 76872 KB Output is correct
15 Correct 283 ms 77016 KB Output is correct
16 Correct 275 ms 76492 KB Output is correct
17 Correct 291 ms 76360 KB Output is correct
18 Correct 284 ms 76368 KB Output is correct
19 Correct 277 ms 77000 KB Output is correct
20 Correct 210 ms 72776 KB Output is correct
21 Correct 120 ms 73288 KB Output is correct
22 Correct 124 ms 74836 KB Output is correct
23 Correct 212 ms 74568 KB Output is correct
24 Correct 225 ms 74548 KB Output is correct
25 Correct 206 ms 73800 KB Output is correct
26 Correct 190 ms 73752 KB Output is correct
27 Correct 197 ms 73660 KB Output is correct
28 Correct 207 ms 74080 KB Output is correct
29 Correct 1095 ms 140356 KB Output is correct
30 Correct 758 ms 137200 KB Output is correct
31 Correct 698 ms 141428 KB Output is correct
32 Correct 927 ms 140356 KB Output is correct
33 Correct 959 ms 140360 KB Output is correct
34 Correct 1010 ms 138204 KB Output is correct
35 Correct 1063 ms 137696 KB Output is correct
36 Correct 992 ms 137800 KB Output is correct
37 Correct 1024 ms 139320 KB Output is correct
38 Correct 815 ms 142912 KB Output is correct
39 Correct 836 ms 142912 KB Output is correct
40 Correct 842 ms 139740 KB Output is correct
41 Correct 852 ms 139228 KB Output is correct
42 Correct 789 ms 139248 KB Output is correct
43 Correct 768 ms 140852 KB Output is correct
44 Correct 891 ms 142640 KB Output is correct
45 Correct 812 ms 142664 KB Output is correct
46 Correct 808 ms 139500 KB Output is correct
47 Correct 859 ms 139080 KB Output is correct
48 Correct 850 ms 139208 KB Output is correct
49 Correct 818 ms 141128 KB Output is correct
50 Correct 938 ms 141896 KB Output is correct
51 Correct 943 ms 141880 KB Output is correct
52 Correct 887 ms 139476 KB Output is correct
53 Correct 857 ms 139224 KB Output is correct
54 Correct 883 ms 139336 KB Output is correct
55 Correct 939 ms 141056 KB Output is correct