oj.uz

답안 #208619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208619 2020-03-11T22:17:07 Z super_j6 3단 점프 (JOI19_jumps) C++14
100 / 100
 1552 ms 111608 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];
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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