oj.uz

Submission #797290

# Submission time Handle Problem Language Result Execution time Memory
797290 2023-07-29T08:51:20 Z ymm Triple Jump (JOI19_jumps) C++17
100 / 100
 868 ms 79304 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 500'010;

namespace seg {
	struct node {
		int ans, mxab, mxc;
	} t[N*4];
	int sz;

	node merge(const node &l, const node &r) {
		node ans;
		ans.ans = max({l.ans, r.ans, l.mxab + r.mxc});
		ans.mxab = max(l.mxab, r.mxab);
		ans.mxc = max(l.mxc, r.mxc);
		return ans;
	}
	void merge(int i) { t[i] = merge(t[2*i+1], t[2*i+2]); }

	void init(const vector<int> &vec, int i, int b, int e) {
		if (e-b == 1) {
			t[i].ans = t[i].mxc = vec[b];
			t[i].mxab = 0;
			return;
		}
		init(vec, 2*i+1, b, (b+e)/2);
		init(vec, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void init(const vector<int> &vec) {
		sz = vec.size();
		init(vec, 0, 0, sz);
	}

	void up(int p, int x, int i, int b, int e) {
		if (e-b == 1) {
			t[i].mxab = max(t[i].mxab, x);
			t[i].ans = t[i].mxab + t[i].mxc;
			return;
		}
		if (p < (b+e)/2)
			up(p, x, 2*i+1, b, (b+e)/2);
		else
			up(p, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void up(int p, int x) { up(p, x, 0, 0, sz); }

	node get(int l, int r, int i, int b, int e) {
		if (l <= b && e <= r)
			return t[i];
		if (l < (b+e)/2 && (b+e)/2 < r) {
			return merge(get(l, r, 2*i+1, b, (b+e)/2),
			             get(l, r, 2*i+2, (b+e)/2, e));
		}
		if (l < (b+e)/2)
			return get(l, r, 2*i+1, b, (b+e)/2);
		else
			return get(l, r, 2*i+2, (b+e)/2, e);
	}
	int get(int l, int r) { return get(l, r, 0, 0, sz).ans; }
}

vector<pii> ab[N];
vector<pii> Q[N];
int ans[N];
int a[N];
int n, q;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n)
		cin >> a[i];
	cin >> q;
	Loop (i,0,q) {
		int l, r;
		cin >> l >> r;
		--l;
		Q[l].push_back({i,r});
	}
	vector<int> st;
	Loop (i,0,n) {
		while (st.size() && a[st.back()] < a[i])
			st.pop_back();
		if (st.size())
			ab[st.back()].push_back({a[i] + a[st.back()], 2*i - st.back()});
		st.push_back(i);
	}
	st.clear();
	LoopR (i,0,n) {
		while (st.size() && a[st.back()] <= a[i])
			st.pop_back();
		if (st.size())
			ab[i].push_back({a[i] + a[st.back()], 2*st.back()-i});
		st.push_back(i);
	}
	seg::init(vector<int>(a, a+n));
	LoopR (i,0,n) {
		for (auto [sum, pos] : ab[i]) {
			if (pos >= n)
				continue;
			seg::up(pos, sum);
		}
		for (auto [q, r] : Q[i])
			ans[q] = seg::get(i, r);
	}
	Loop (i,0,q)
		cout << ans[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 14 ms 23824 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 13 ms 23776 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 11 ms 23744 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 13 ms 23764 KB Output is correct
3 Correct 14 ms 23824 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 13 ms 23776 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 11 ms 23744 KB Output is correct
11 Correct 205 ms 37928 KB Output is correct
12 Correct 224 ms 37852 KB Output is correct
13 Correct 228 ms 37880 KB Output is correct
14 Correct 238 ms 37928 KB Output is correct
15 Correct 216 ms 37904 KB Output is correct
16 Correct 216 ms 37320 KB Output is correct
17 Correct 218 ms 37284 KB Output is correct
18 Correct 235 ms 37124 KB Output is correct
19 Correct 224 ms 37732 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 38964 KB Output is correct
2 Correct 85 ms 38500 KB Output is correct
3 Correct 90 ms 38480 KB Output is correct
4 Correct 141 ms 39008 KB Output is correct
5 Correct 141 ms 39008 KB Output is correct
6 Correct 135 ms 38916 KB Output is correct
7 Correct 135 ms 39008 KB Output is correct
8 Correct 149 ms 38940 KB Output is correct
9 Correct 133 ms 38928 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 13 ms 23764 KB Output is correct
3 Correct 14 ms 23824 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 13 ms 23776 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 11 ms 23744 KB Output is correct
11 Correct 205 ms 37928 KB Output is correct
12 Correct 224 ms 37852 KB Output is correct
13 Correct 228 ms 37880 KB Output is correct
14 Correct 238 ms 37928 KB Output is correct
15 Correct 216 ms 37904 KB Output is correct
16 Correct 216 ms 37320 KB Output is correct
17 Correct 218 ms 37284 KB Output is correct
18 Correct 235 ms 37124 KB Output is correct
19 Correct 224 ms 37732 KB Output is correct
20 Correct 141 ms 38964 KB Output is correct
21 Correct 85 ms 38500 KB Output is correct
22 Correct 90 ms 38480 KB Output is correct
23 Correct 141 ms 39008 KB Output is correct
24 Correct 141 ms 39008 KB Output is correct
25 Correct 135 ms 38916 KB Output is correct
26 Correct 135 ms 39008 KB Output is correct
27 Correct 149 ms 38940 KB Output is correct
28 Correct 133 ms 38928 KB Output is correct
29 Correct 868 ms 73616 KB Output is correct
30 Correct 636 ms 72500 KB Output is correct
31 Correct 712 ms 72432 KB Output is correct
32 Correct 778 ms 73632 KB Output is correct
33 Correct 838 ms 73636 KB Output is correct
34 Correct 754 ms 73008 KB Output is correct
35 Correct 738 ms 72928 KB Output is correct
36 Correct 751 ms 73008 KB Output is correct
37 Correct 738 ms 73528 KB Output is correct
38 Correct 557 ms 79272 KB Output is correct
39 Correct 576 ms 79304 KB Output is correct
40 Correct 547 ms 77648 KB Output is correct
41 Correct 546 ms 77300 KB Output is correct
42 Correct 544 ms 77408 KB Output is correct
43 Correct 554 ms 78392 KB Output is correct
44 Correct 609 ms 78576 KB Output is correct
45 Correct 591 ms 78684 KB Output is correct
46 Correct 582 ms 77204 KB Output is correct
47 Correct 587 ms 76928 KB Output is correct
48 Correct 591 ms 77224 KB Output is correct
49 Correct 599 ms 78264 KB Output is correct
50 Correct 660 ms 76532 KB Output is correct
51 Correct 644 ms 76544 KB Output is correct
52 Correct 642 ms 75748 KB Output is correct
53 Correct 641 ms 75644 KB Output is correct
54 Correct 673 ms 75612 KB Output is correct
55 Correct 660 ms 76404 KB Output is correct