Submission #208619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208619	2020-03-11T22:17:07 Z	super_j6	Triple Jump (JOI19_jumps)	C++14	100 / 100	1552 ms	111608 KB

jumps

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define pii pair<int, pi>
#define f first
#define s second

struct segTree{
	int l, r;
	segTree *left, *right;
	pii val = {0, {0, 0}};
	
	segTree(int a, int b){
		l = a;
		r = b;
		
		if(l != r){
			int mid = (l + r) / 2;
			left = new segTree(l, mid);
			right = new segTree(mid + 1, r);
		}
	}
	
	pii pull(pii lq, pii rq){
		return {max(lq.s.f + rq.s.s, max(lq.f, rq.f)), {max(lq.s.f, rq.s.f), max(lq.s.s, rq.s.s)}};
	}
	
	void add(int x, pi v){
		if(x < l || r < x) return;
		if(l == r){
			val.s.f = max(val.s.f, v.f);
			val.s.s = max(val.s.s, v.s);
			val.f = val.s.f + val.s.s;
			return;
		}
		
		left->add(x, v);
		right->add(x, v);
		val = pull(left->val, right->val);
	}
	
	pii qry(int a, int b){
		if(r < a || b < l) return {0, {0, 0}};
		if(a <= l && r <= b) return val;
		
		return pull(left->qry(a, b), right->qry(a, b));
	}
};

const int maxn = 500000;
int n, q;
int a[maxn];
vector<int> p[maxn];
vector<pi> qry[maxn];
int ans[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	stack<int> stk;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		while(!stk.empty()){
			int j = stk.top(), k = 2 * i - j;
			if(k < n) p[j].push_back(k);
			if(a[j] <= a[i]) stk.pop();
			else break;
		}
		stk.push(i);
	}
	
	cin >> q;
	
	for(int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		l--, r--;
		qry[l].push_back({r, i});
	}
	
	segTree tre(0, n);
	for(int i = n - 1; i >= 0; i--){
		tre.add(i, {0, a[i]});
		for(int j : p[i]) tre.add(j, {a[i] + a[(i + j) / 2], 0});
		for(pi j : qry[i]) ans[j.s] = tre.qry(i, j.f).f;
	}
	
	for(int i = 0; i < q; i++) cout << ans[i] << endl;

	return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	24056 KB	Output is correct
2	Correct	19 ms	23800 KB	Output is correct
3	Correct	19 ms	23800 KB	Output is correct
4	Correct	19 ms	23800 KB	Output is correct
5	Correct	19 ms	23800 KB	Output is correct
6	Correct	19 ms	23800 KB	Output is correct
7	Correct	20 ms	23800 KB	Output is correct
8	Correct	20 ms	23800 KB	Output is correct
9	Correct	19 ms	23904 KB	Output is correct
10	Correct	19 ms	23800 KB	Output is correct

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	24056 KB	Output is correct
2	Correct	19 ms	23800 KB	Output is correct
3	Correct	19 ms	23800 KB	Output is correct
4	Correct	19 ms	23800 KB	Output is correct
5	Correct	19 ms	23800 KB	Output is correct
6	Correct	19 ms	23800 KB	Output is correct
7	Correct	20 ms	23800 KB	Output is correct
8	Correct	20 ms	23800 KB	Output is correct
9	Correct	19 ms	23904 KB	Output is correct
10	Correct	19 ms	23800 KB	Output is correct
11	Correct	300 ms	37368 KB	Output is correct
12	Correct	322 ms	37368 KB	Output is correct
13	Correct	302 ms	37368 KB	Output is correct
14	Correct	312 ms	37368 KB	Output is correct
15	Correct	310 ms	37368 KB	Output is correct
16	Correct	306 ms	36728 KB	Output is correct
17	Correct	312 ms	36856 KB	Output is correct
18	Correct	300 ms	36600 KB	Output is correct
19	Correct	300 ms	37240 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	281 ms	49912 KB	Output is correct
2	Correct	200 ms	49656 KB	Output is correct
3	Correct	202 ms	50424 KB	Output is correct
4	Correct	282 ms	49912 KB	Output is correct
5	Correct	285 ms	49912 KB	Output is correct
6	Correct	271 ms	49912 KB	Output is correct
7	Correct	280 ms	50040 KB	Output is correct
8	Correct	274 ms	49912 KB	Output is correct
9	Correct	282 ms	49912 KB	Output is correct

Subtask #4
54.0 / 54.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	24056 KB	Output is correct
2	Correct	19 ms	23800 KB	Output is correct
3	Correct	19 ms	23800 KB	Output is correct
4	Correct	19 ms	23800 KB	Output is correct
5	Correct	19 ms	23800 KB	Output is correct
6	Correct	19 ms	23800 KB	Output is correct
7	Correct	20 ms	23800 KB	Output is correct
8	Correct	20 ms	23800 KB	Output is correct
9	Correct	19 ms	23904 KB	Output is correct
10	Correct	19 ms	23800 KB	Output is correct
11	Correct	300 ms	37368 KB	Output is correct
12	Correct	322 ms	37368 KB	Output is correct
13	Correct	302 ms	37368 KB	Output is correct
14	Correct	312 ms	37368 KB	Output is correct
15	Correct	310 ms	37368 KB	Output is correct
16	Correct	306 ms	36728 KB	Output is correct
17	Correct	312 ms	36856 KB	Output is correct
18	Correct	300 ms	36600 KB	Output is correct
19	Correct	300 ms	37240 KB	Output is correct
20	Correct	281 ms	49912 KB	Output is correct
21	Correct	200 ms	49656 KB	Output is correct
22	Correct	202 ms	50424 KB	Output is correct
23	Correct	282 ms	49912 KB	Output is correct
24	Correct	285 ms	49912 KB	Output is correct
25	Correct	271 ms	49912 KB	Output is correct
26	Correct	280 ms	50040 KB	Output is correct
27	Correct	274 ms	49912 KB	Output is correct
28	Correct	282 ms	49912 KB	Output is correct
29	Correct	1541 ms	105976 KB	Output is correct
30	Correct	1338 ms	105296 KB	Output is correct
31	Correct	1329 ms	107244 KB	Output is correct
32	Correct	1552 ms	105848 KB	Output is correct
33	Correct	1540 ms	105900 KB	Output is correct
34	Correct	1544 ms	105296 KB	Output is correct
35	Correct	1530 ms	105208 KB	Output is correct
36	Correct	1526 ms	105336 KB	Output is correct
37	Correct	1547 ms	105848 KB	Output is correct
38	Correct	1059 ms	111608 KB	Output is correct
39	Correct	1062 ms	111540 KB	Output is correct
40	Correct	1039 ms	109936 KB	Output is correct
41	Correct	1020 ms	109664 KB	Output is correct
42	Correct	1042 ms	109816 KB	Output is correct
43	Correct	1053 ms	110588 KB	Output is correct
44	Correct	1122 ms	110840 KB	Output is correct
45	Correct	1107 ms	111096 KB	Output is correct
46	Correct	1085 ms	109560 KB	Output is correct
47	Correct	1087 ms	109320 KB	Output is correct
48	Correct	1104 ms	109304 KB	Output is correct
49	Correct	1094 ms	110584 KB	Output is correct
50	Correct	1211 ms	109048 KB	Output is correct
51	Correct	1206 ms	109320 KB	Output is correct
52	Correct	1202 ms	108280 KB	Output is correct
53	Correct	1208 ms	108104 KB	Output is correct
54	Correct	1201 ms	108072 KB	Output is correct
55	Correct	1182 ms	109080 KB	Output is correct

Submission #208619

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