Submission #237204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
237204	2020-06-05T08:53:43 Z	manh9203	Triple Jump (JOI19_jumps)	C++17	100 / 100	1483 ms	108280 KB

jumps

#include<bits/stdc++.h>

using namespace std;

#define ll long long
const int N = 5e5 + 5;

ll n, a[N];
int q, L[N], R[N];
vector<int> queRy[N];
vector<int> add[N];
ll ans[N];

struct node {
	ll D, C, lz;
} st[4 * N];

void build(int id, int l, int r) {
	if (l == r) {
		st[id].C = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	st[id].D = max(st[id << 1].D, st[id << 1 | 1].D);
	st[id].C = max(st[id << 1].C, st[id << 1 | 1].C);
}

void pushDown(int id, int l, int r) {
	if (st[id].lz != 0) {
		st[id].D = max(st[id].D, st[id].C + st[id].lz);
		if (l < r) {
			st[id << 1].lz = max(st[id << 1].lz, st[id].lz);
			st[id << 1 | 1].lz = max(st[id << 1 | 1].lz, st[id].lz); 
		}
		st[id].lz = 0;
	}
}
void update(int id, int l, int r, int i, int j, int x) {
	pushDown(id, l, r);
	if (l > j || r < i || i > j) {
		return;
	}
	if (l >= i && r <= j) {
		st[id].lz = x;
		pushDown(id, l, r);
		return;
	}
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, i, j, x);
	update(id << 1 | 1, mid + 1, r, i, j, x);
	st[id].D = max(st[id << 1].D, st[id << 1 | 1].D);
}
ll get(int id, int l, int r, int i, int j) {
	pushDown(id, l, r);
	if (l > j || r < i || i > j) {
		return 0;
	}
	if (l >= i && r <= j) {
		return st[id].D;
	}
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, i, j), get(id << 1 | 1, mid + 1, r, i, j));
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> L[i] >> R[i];
		queRy[L[i]].push_back(i);
	}
	
	vector<int> s;
	for (int i = 1; i <= n; i++) {
		while (s.size() > 0 && a[s.back()] < a[i]) {
			s.pop_back();
		}
		if (s.size() > 0) {
			add[s.back()].push_back(i);
		}
		s.push_back(i);
	}
	
	s.clear();
	for (int i = n; i >= 1; i--) {
		while (s.size() > 0 && a[s.back()] < a[i]) {
			s.pop_back();
		}
		if (s.size() > 0) {
			add[i].push_back(s.back());
		}
		s.push_back(i);
	}
	
	build(1, 1, n);
	for (int i = n; i >= 1; i--) {
		for (int j : add[i]) {
			update(1, 1, n, 2 * j - i, n, a[i] + a[j]);
		}
		for (int j : queRy[i]) {
			ans[j] = get(1, 1, n, L[j], R[j]);
		}
	}
	
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << "\n";
	}
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	18 ms	23808 KB	Output is correct
5	Correct	20 ms	23808 KB	Output is correct
6	Correct	19 ms	23936 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	20 ms	23808 KB	Output is correct
9	Correct	18 ms	23808 KB	Output is correct
10	Correct	20 ms	23808 KB	Output is correct

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	18 ms	23808 KB	Output is correct
5	Correct	20 ms	23808 KB	Output is correct
6	Correct	19 ms	23936 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	20 ms	23808 KB	Output is correct
9	Correct	18 ms	23808 KB	Output is correct
10	Correct	20 ms	23808 KB	Output is correct
11	Correct	388 ms	45176 KB	Output is correct
12	Correct	441 ms	45176 KB	Output is correct
13	Correct	389 ms	45156 KB	Output is correct
14	Correct	370 ms	45048 KB	Output is correct
15	Correct	384 ms	45176 KB	Output is correct
16	Correct	374 ms	44408 KB	Output is correct
17	Correct	397 ms	44408 KB	Output is correct
18	Correct	392 ms	44428 KB	Output is correct
19	Correct	393 ms	45048 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	220 ms	45948 KB	Output is correct
2	Correct	131 ms	46572 KB	Output is correct
3	Correct	124 ms	46700 KB	Output is correct
4	Correct	223 ms	46092 KB	Output is correct
5	Correct	212 ms	46072 KB	Output is correct
6	Correct	199 ms	45304 KB	Output is correct
7	Correct	202 ms	45308 KB	Output is correct
8	Correct	201 ms	45176 KB	Output is correct
9	Correct	236 ms	45560 KB	Output is correct

Subtask #4
54.0 / 54.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	18 ms	23808 KB	Output is correct
5	Correct	20 ms	23808 KB	Output is correct
6	Correct	19 ms	23936 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	20 ms	23808 KB	Output is correct
9	Correct	18 ms	23808 KB	Output is correct
10	Correct	20 ms	23808 KB	Output is correct
11	Correct	388 ms	45176 KB	Output is correct
12	Correct	441 ms	45176 KB	Output is correct
13	Correct	389 ms	45156 KB	Output is correct
14	Correct	370 ms	45048 KB	Output is correct
15	Correct	384 ms	45176 KB	Output is correct
16	Correct	374 ms	44408 KB	Output is correct
17	Correct	397 ms	44408 KB	Output is correct
18	Correct	392 ms	44428 KB	Output is correct
19	Correct	393 ms	45048 KB	Output is correct
20	Correct	220 ms	45948 KB	Output is correct
21	Correct	131 ms	46572 KB	Output is correct
22	Correct	124 ms	46700 KB	Output is correct
23	Correct	223 ms	46092 KB	Output is correct
24	Correct	212 ms	46072 KB	Output is correct
25	Correct	199 ms	45304 KB	Output is correct
26	Correct	202 ms	45308 KB	Output is correct
27	Correct	201 ms	45176 KB	Output is correct
28	Correct	236 ms	45560 KB	Output is correct
29	Correct	1483 ms	101408 KB	Output is correct
30	Correct	1230 ms	102732 KB	Output is correct
31	Correct	1152 ms	102840 KB	Output is correct
32	Correct	1380 ms	101392 KB	Output is correct
33	Correct	1386 ms	101368 KB	Output is correct
34	Correct	1378 ms	99448 KB	Output is correct
35	Correct	1405 ms	98808 KB	Output is correct
36	Correct	1388 ms	98936 KB	Output is correct
37	Correct	1420 ms	100216 KB	Output is correct
38	Correct	988 ms	108156 KB	Output is correct
39	Correct	949 ms	108280 KB	Output is correct
40	Correct	978 ms	104696 KB	Output is correct
41	Correct	953 ms	104312 KB	Output is correct
42	Correct	917 ms	104252 KB	Output is correct
43	Correct	965 ms	106104 KB	Output is correct
44	Correct	1051 ms	107256 KB	Output is correct
45	Correct	1036 ms	107336 KB	Output is correct
46	Correct	973 ms	104184 KB	Output is correct
47	Correct	993 ms	103764 KB	Output is correct
48	Correct	997 ms	103860 KB	Output is correct
49	Correct	961 ms	105808 KB	Output is correct
50	Correct	1126 ms	105184 KB	Output is correct
51	Correct	1091 ms	105340 KB	Output is correct
52	Correct	1092 ms	102952 KB	Output is correct
53	Correct	1073 ms	102520 KB	Output is correct
54	Correct	1107 ms	102392 KB	Output is correct
55	Correct	1087 ms	104084 KB	Output is correct

Submission #237204

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 14.0 / 14.0

Subtask #3 27.0 / 27.0

Subtask #4 54.0 / 54.0

Subtask #1
5.0 / 5.0

Subtask #2
14.0 / 14.0

Subtask #3
27.0 / 27.0

Subtask #4
54.0 / 54.0