oj.uz

Submission #757114

# Submission time Handle Problem Language Result Execution time Memory
757114 2023-06-12T16:31:26 Z jmyszka2007 Triple Jump (JOI19_jumps) C++17
100 / 100
 1750 ms 91468 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define vi vector<int>
#define pb push_back
//max1 = A + B, max2 = C, max3 = A + B + C
struct node {
	int max1, max2, max3;
};
constexpr int base = (1 << 19);
constexpr int LIM = 5e5;
node INF;
node tri[2 * base];
int tab[LIM + 10];
vi can[LIM + 10];
vector<pi> zap[LIM + 10];
int ans[LIM + 10];
int lasy[2 * base];
node merge(node a, node b) {
	node res;
	res.max1 = max(a.max1, b.max1);
	res.max2 = max(a.max2, b.max2);
	res.max3 = max({a.max3, b.max3, a.max1 + b.max2});
	return res;
}
void spl(int v) {
	tri[2 * v].max1 = max(tri[2 * v].max1, lasy[v]);
	tri[2 * v].max3 = max(tri[2 * v].max3, lasy[v] + tri[2 * v].max2);
	tri[2 * v + 1].max1 = max(tri[2 * v + 1].max1, lasy[v]);
	tri[2 * v + 1].max3 = max(tri[2 * v + 1].max3, lasy[v] + tri[2 * v + 1].max2);
	lasy[2 * v] = max(lasy[2 * v], lasy[v]);
	lasy[2 * v + 1] = max(lasy[2 * v + 1], lasy[v]);
}
void upd(int v, int l, int r, int a, int b, int x) {
	if(l > b || r < a) {
		return;
	}
	if(a <= l && r <= b) {
		tri[v].max1 = max(tri[v].max1, x);
		tri[v].max3 = max(tri[v].max3, x + tri[v].max2);
		lasy[v] = max(lasy[v], x);
		return;
	}
	spl(v);
	int mid = (l + r) / 2;
	upd(2 * v, l, mid, a, b, x);
	upd(2 * v + 1, mid + 1, r, a, b, x);
	tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
node res;
void query(int v, int l, int r, int a, int b) {
	if(l > b || r < a) {
		return;
	}
	if(a <= l && r <= b) {
		res = merge(res, tri[v]);
		return;
	}
	spl(v);
	int mid = (l + r) / 2;
	query(2 * v, l, mid, a, b);
	query(2 * v + 1, mid + 1, r, a, b);
	tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	INF.max1 = -1e9, INF.max2 = -1e9, INF.max3 = -1e9; 
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> tab[i];
		tri[i + base - 1] = INF;
		tri[i + base - 1].max2 = tab[i];
	}
	for(int i = base - 1; i >= 1; i--) {
		tri[i] = merge(tri[2 * i], tri[2 * i + 1]);
	}
	stack<int>s;
	for(int i = 1; i <= n; i++) {
		while(!s.empty() && tab[s.top()] <= tab[i]) {
			can[s.top()].pb(i);
			s.pop();
		}
		if(!s.empty()) {
			can[s.top()].pb(i);
		}
		s.push(i);
	}
	int t;
	cin >> t;
	for(int i = 1; i <= t; i++) {
		int l, r;
		cin >> l >> r;
		zap[l].pb({r, i});
	}
	for(int i = n; i >= 1; i--) {
		for(auto x : can[i]) {
			upd(1, 1, base, 2 * x - i, n, tab[i] + tab[x]);
		}
		for(auto x : zap[i]) {
			res = INF;
			query(1, 1, base, i, x.st);
			ans[x.nd] = res.max3;
		}
	}
	for(int i = 1; i <= t; i++) {
		cout << ans[i] << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 30000 KB Output is correct
2 Correct 22 ms 29952 KB Output is correct
3 Correct 22 ms 29964 KB Output is correct
4 Correct 22 ms 29980 KB Output is correct
5 Correct 21 ms 30024 KB Output is correct
6 Correct 22 ms 30036 KB Output is correct
7 Correct 22 ms 29964 KB Output is correct
8 Correct 22 ms 30060 KB Output is correct
9 Correct 21 ms 29984 KB Output is correct
10 Correct 23 ms 30028 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 30000 KB Output is correct
2 Correct 22 ms 29952 KB Output is correct
3 Correct 22 ms 29964 KB Output is correct
4 Correct 22 ms 29980 KB Output is correct
5 Correct 21 ms 30024 KB Output is correct
6 Correct 22 ms 30036 KB Output is correct
7 Correct 22 ms 29964 KB Output is correct
8 Correct 22 ms 30060 KB Output is correct
9 Correct 21 ms 29984 KB Output is correct
10 Correct 23 ms 30028 KB Output is correct
11 Correct 515 ms 48912 KB Output is correct
12 Correct 531 ms 48772 KB Output is correct
13 Correct 512 ms 48888 KB Output is correct
14 Correct 525 ms 48996 KB Output is correct
15 Correct 522 ms 48912 KB Output is correct
16 Correct 553 ms 48268 KB Output is correct
17 Correct 568 ms 48164 KB Output is correct
18 Correct 523 ms 48208 KB Output is correct
19 Correct 509 ms 48660 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 41384 KB Output is correct
2 Correct 200 ms 41268 KB Output is correct
3 Correct 186 ms 42068 KB Output is correct
4 Correct 350 ms 41564 KB Output is correct
5 Correct 341 ms 41524 KB Output is correct
6 Correct 331 ms 41540 KB Output is correct
7 Correct 344 ms 41548 KB Output is correct
8 Correct 338 ms 41536 KB Output is correct
9 Correct 359 ms 41448 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 30000 KB Output is correct
2 Correct 22 ms 29952 KB Output is correct
3 Correct 22 ms 29964 KB Output is correct
4 Correct 22 ms 29980 KB Output is correct
5 Correct 21 ms 30024 KB Output is correct
6 Correct 22 ms 30036 KB Output is correct
7 Correct 22 ms 29964 KB Output is correct
8 Correct 22 ms 30060 KB Output is correct
9 Correct 21 ms 29984 KB Output is correct
10 Correct 23 ms 30028 KB Output is correct
11 Correct 515 ms 48912 KB Output is correct
12 Correct 531 ms 48772 KB Output is correct
13 Correct 512 ms 48888 KB Output is correct
14 Correct 525 ms 48996 KB Output is correct
15 Correct 522 ms 48912 KB Output is correct
16 Correct 553 ms 48268 KB Output is correct
17 Correct 568 ms 48164 KB Output is correct
18 Correct 523 ms 48208 KB Output is correct
19 Correct 509 ms 48660 KB Output is correct
20 Correct 344 ms 41384 KB Output is correct
21 Correct 200 ms 41268 KB Output is correct
22 Correct 186 ms 42068 KB Output is correct
23 Correct 350 ms 41564 KB Output is correct
24 Correct 341 ms 41524 KB Output is correct
25 Correct 331 ms 41540 KB Output is correct
26 Correct 344 ms 41548 KB Output is correct
27 Correct 338 ms 41536 KB Output is correct
28 Correct 359 ms 41448 KB Output is correct
29 Correct 1716 ms 85804 KB Output is correct
30 Correct 1263 ms 85316 KB Output is correct
31 Correct 1292 ms 87128 KB Output is correct
32 Correct 1687 ms 85876 KB Output is correct
33 Correct 1715 ms 85744 KB Output is correct
34 Correct 1671 ms 83624 KB Output is correct
35 Correct 1706 ms 83188 KB Output is correct
36 Correct 1730 ms 83220 KB Output is correct
37 Correct 1750 ms 84572 KB Output is correct
38 Correct 1374 ms 91468 KB Output is correct
39 Correct 1346 ms 91464 KB Output is correct
40 Correct 1373 ms 88072 KB Output is correct
41 Correct 1339 ms 87820 KB Output is correct
42 Correct 1362 ms 87708 KB Output is correct
43 Correct 1366 ms 89360 KB Output is correct
44 Correct 1435 ms 91108 KB Output is correct
45 Correct 1430 ms 90856 KB Output is correct
46 Correct 1415 ms 87704 KB Output is correct
47 Correct 1443 ms 87312 KB Output is correct
48 Correct 1458 ms 87288 KB Output is correct
49 Correct 1402 ms 89496 KB Output is correct
50 Correct 1559 ms 89004 KB Output is correct
51 Correct 1540 ms 88968 KB Output is correct
52 Correct 1513 ms 86484 KB Output is correct
53 Correct 1492 ms 86168 KB Output is correct
54 Correct 1465 ms 86284 KB Output is correct
55 Correct 1595 ms 88040 KB Output is correct