oj.uz

Submission #208618

# Submission time Handle Problem Language Result Execution time Memory
208618 2020-03-11T22:13:42 Z super_j6 Triple Jump (JOI19_jumps) C++14
100 / 100
 1659 ms 112248 KB 
#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], b[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 19 ms 23800 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 19 ms 23804 KB Output is correct
4 Correct 19 ms 23928 KB Output is correct
5 Correct 19 ms 23800 KB Output is correct
6 Correct 19 ms 23932 KB Output is correct
7 Correct 19 ms 23800 KB Output is correct
8 Correct 22 ms 24184 KB Output is correct
9 Correct 20 ms 23800 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 19 ms 23800 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 19 ms 23804 KB Output is correct
4 Correct 19 ms 23928 KB Output is correct
5 Correct 19 ms 23800 KB Output is correct
6 Correct 19 ms 23932 KB Output is correct
7 Correct 19 ms 23800 KB Output is correct
8 Correct 22 ms 24184 KB Output is correct
9 Correct 20 ms 23800 KB Output is correct
10 Correct 19 ms 23800 KB Output is correct
11 Correct 318 ms 38008 KB Output is correct
12 Correct 298 ms 37876 KB Output is correct
13 Correct 306 ms 38008 KB Output is correct
14 Correct 300 ms 38008 KB Output is correct
15 Correct 307 ms 38008 KB Output is correct
16 Correct 301 ms 37368 KB Output is correct
17 Correct 311 ms 37308 KB Output is correct
18 Correct 311 ms 37368 KB Output is correct
19 Correct 314 ms 37880 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 50680 KB Output is correct
2 Correct 211 ms 50296 KB Output is correct
3 Correct 203 ms 51064 KB Output is correct
4 Correct 286 ms 50552 KB Output is correct
5 Correct 290 ms 50680 KB Output is correct
6 Correct 283 ms 50680 KB Output is correct
7 Correct 279 ms 50552 KB Output is correct
8 Correct 273 ms 50552 KB Output is correct
9 Correct 287 ms 50808 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23800 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 19 ms 23804 KB Output is correct
4 Correct 19 ms 23928 KB Output is correct
5 Correct 19 ms 23800 KB Output is correct
6 Correct 19 ms 23932 KB Output is correct
7 Correct 19 ms 23800 KB Output is correct
8 Correct 22 ms 24184 KB Output is correct
9 Correct 20 ms 23800 KB Output is correct
10 Correct 19 ms 23800 KB Output is correct
11 Correct 318 ms 38008 KB Output is correct
12 Correct 298 ms 37876 KB Output is correct
13 Correct 306 ms 38008 KB Output is correct
14 Correct 300 ms 38008 KB Output is correct
15 Correct 307 ms 38008 KB Output is correct
16 Correct 301 ms 37368 KB Output is correct
17 Correct 311 ms 37308 KB Output is correct
18 Correct 311 ms 37368 KB Output is correct
19 Correct 314 ms 37880 KB Output is correct
20 Correct 289 ms 50680 KB Output is correct
21 Correct 211 ms 50296 KB Output is correct
22 Correct 203 ms 51064 KB Output is correct
23 Correct 286 ms 50552 KB Output is correct
24 Correct 290 ms 50680 KB Output is correct
25 Correct 283 ms 50680 KB Output is correct
26 Correct 279 ms 50552 KB Output is correct
27 Correct 273 ms 50552 KB Output is correct
28 Correct 287 ms 50808 KB Output is correct
29 Correct 1553 ms 106616 KB Output is correct
30 Correct 1334 ms 105848 KB Output is correct
31 Correct 1429 ms 108028 KB Output is correct
32 Correct 1613 ms 106744 KB Output is correct
33 Correct 1633 ms 106588 KB Output is correct
34 Correct 1586 ms 105852 KB Output is correct
35 Correct 1600 ms 105976 KB Output is correct
36 Correct 1659 ms 105848 KB Output is correct
37 Correct 1570 ms 106360 KB Output is correct
38 Correct 1067 ms 112248 KB Output is correct
39 Correct 1085 ms 112124 KB Output is correct
40 Correct 1040 ms 110328 KB Output is correct
41 Correct 1035 ms 110072 KB Output is correct
42 Correct 1046 ms 110072 KB Output is correct
43 Correct 1073 ms 111032 KB Output is correct
44 Correct 1129 ms 111356 KB Output is correct
45 Correct 1195 ms 111224 KB Output is correct
46 Correct 1139 ms 109684 KB Output is correct
47 Correct 1104 ms 109688 KB Output is correct
48 Correct 1116 ms 109432 KB Output is correct
49 Correct 1105 ms 110968 KB Output is correct
50 Correct 1223 ms 109304 KB Output is correct
51 Correct 1263 ms 109176 KB Output is correct
52 Correct 1233 ms 108296 KB Output is correct
53 Correct 1260 ms 108408 KB Output is correct
54 Correct 1202 ms 108468 KB Output is correct
55 Correct 1202 ms 109052 KB Output is correct