oj.uz

Submission #566890

# Submission time Handle Problem Language Result Execution time Memory
566890 2022-05-23T05:38:26 Z amunduzbaev Rainforest Jumps (APIO21_jumps) C++17
31 / 100
 4000 ms 78324 KB 
#include "jumps.h"

#ifndef EVAL
#include "stub.cpp"
#endif

#include "bits/stdc++.h"
using namespace std;

const int B = 205;
const int N = 2e5 + 5;
const int lg = 18;
int mx[N][lg], mn[N][lg], h[N], pos[N];
int lx[N], rx[N], prec[N/B][N];

struct ST{
	vector<int> tree[N << 2];
	int mx[N << 2];
	void build(int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x].push_back(h[lx]); return; }
		int m = (lx + rx) >> 1;
		build(lx, m, x << 1);
		build(m + 1, rx, x << 1 | 1);
		tree[x].insert(tree[x].end(), tree[x<<1].begin(), tree[x<<1].end());
		tree[x].insert(tree[x].end(), tree[x<<1|1].begin(), tree[x<<1|1].end());
		sort(tree[x].begin(), tree[x].end());
		mx[x] = max(mx[x<<1], mx[x<<1|1]);
	}
	
	int get_(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(mx[x] <= v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(mx[x << 1 | 1] > v) return get_(l, r, v, m + 1, rx, x<<1 | 1);
			else return get_(l, r, v, lx, m, x << 1);
		} int m = (lx + rx) >> 1;
		int R = get_(l, r, v, m + 1, rx, x << 1 | 1);
		if(~R) return R;
		return get_(l, r, v, lx, m, x << 1);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r) return mx[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;

void init(int n, vector<int> H){
	for(int i=0;i<n;i++){
		h[i] = H[i];
		pos[h[i]] = i;
	}
	vector<int> ss;
	for(int i=0;i<n;i++){
		while(!ss.empty() && h[ss.back()] < h[i]) ss.pop_back();
		if(!ss.empty()) lx[i] = ss.back();
		else lx[i] = n;
		ss.push_back(i);
	} ss.clear();
	for(int i=n-1;~i;i--){
		while(!ss.empty() && h[ss.back()] < h[i]) ss.pop_back();
		if(!ss.empty()) rx[i] = ss.back();
		else rx[i] = n;
		ss.push_back(i);
	} ss.clear();
	h[n] = N;
	tree.build();
	for(int i=0;i<n;i++){
		if(h[lx[i]] < h[rx[i]]){
			swap(lx[i], rx[i]);
		} 
		mn[i][0] = rx[i];
		mx[i][0] = lx[i];
	}
	mn[n][0] = mx[n][0] = n;
	//~ for(int i=0;i<n;i++) cout<<mn[i][0]<<" ";
	//~ cout<<"\n";
	//~ for(int i=0;i<n;i++) cout<<mx[i][0]<<" ";
	//~ cout<<"\n";
	
	for(int j=1;j<lg;j++){
		for(int i=0;i<=n;i++){
			mn[i][j] = mn[mn[i][j-1]][j-1];
			mx[i][j] = mx[mx[i][j-1]][j-1];
		}
	}
}

int check(int a, int c){
	int res = 0;
	for(int i=lg-1;~i;i--){
		if(h[mx[a][i]] <= h[c]){
			//~ cout<<mx[a][i]<<" "<<h[mx[a][i]]<<" "<<h[c]<<"\n";
			//~ cout<<i<<"\n";
			a = mx[a][i], res += (1 << i);
		}
	}
	for(int i=lg-1;~i;i--){
		if(h[mn[a][i]] <= h[c]){
			//~ cout<<mx[a][i]<<" "<<h[mx[a][i]]<<" "<<h[c]<<"\n";
			a = mn[a][i], res += (1 << i);
		}
	}
	
	if(a != c) return N;
	return res;
}

int minimum_jumps(int a, int b, int c, int d) {
	//~ int l = max(a, tree.get_(a, b, h[c]) + 1);
	//~ if(l > b) return -1;
	//~ a = tree.get(l, b);
	//~ return check(pos[a], c);
	int res = N;	
	for(int i=c;i<=d;i++){
		int mx = b + 1;
		for(int j=b;j>=a;j--){
			if(h[j] > h[i]) break;
			if(mx > b || h[j] > h[mx]) mx = j;
			res = min(res, check(j, i));
		}
		
		if(mx <= b) res = min(res, check(mx, i));
	}
	if(res == N) return -1;
	return res;
}

/*

7 2
3 2 1 6 4 5 7
4 4 6 6
0 1 2 2

*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 44676 KB Output is correct
2 Correct 96 ms 44672 KB Output is correct
3 Execution timed out 4056 ms 71424 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 44676 KB Output is correct
2 Correct 93 ms 44676 KB Output is correct
3 Correct 89 ms 44604 KB Output is correct
4 Correct 93 ms 44676 KB Output is correct
5 Correct 89 ms 44632 KB Output is correct
6 Correct 91 ms 44676 KB Output is correct
7 Correct 91 ms 44604 KB Output is correct
8 Correct 95 ms 44612 KB Output is correct
9 Correct 94 ms 44560 KB Output is correct
10 Correct 90 ms 44636 KB Output is correct
11 Correct 108 ms 44584 KB Output is correct
12 Correct 106 ms 44592 KB Output is correct
13 Correct 100 ms 44628 KB Output is correct
14 Correct 91 ms 44656 KB Output is correct
15 Correct 99 ms 44568 KB Output is correct
16 Correct 107 ms 44584 KB Output is correct
17 Correct 90 ms 44656 KB Output is correct
18 Correct 87 ms 44612 KB Output is correct
19 Correct 89 ms 44680 KB Output is correct
20 Correct 98 ms 44624 KB Output is correct
21 Correct 95 ms 44656 KB Output is correct
22 Correct 90 ms 44672 KB Output is correct
23 Correct 97 ms 44636 KB Output is correct
24 Correct 92 ms 44576 KB Output is correct
25 Correct 91 ms 44672 KB Output is correct
26 Correct 93 ms 44684 KB Output is correct
27 Correct 92 ms 44644 KB Output is correct
28 Correct 90 ms 44676 KB Output is correct
29 Correct 91 ms 44620 KB Output is correct
30 Correct 90 ms 44684 KB Output is correct
31 Correct 94 ms 44600 KB Output is correct
32 Correct 89 ms 44696 KB Output is correct
33 Correct 87 ms 44596 KB Output is correct
34 Correct 88 ms 44632 KB Output is correct
35 Correct 87 ms 44668 KB Output is correct
36 Correct 95 ms 44696 KB Output is correct
37 Correct 87 ms 44672 KB Output is correct
38 Correct 91 ms 44676 KB Output is correct
39 Correct 89 ms 44676 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 44676 KB Output is correct
2 Correct 93 ms 44676 KB Output is correct
3 Correct 89 ms 44604 KB Output is correct
4 Correct 93 ms 44676 KB Output is correct
5 Correct 89 ms 44632 KB Output is correct
6 Correct 91 ms 44676 KB Output is correct
7 Correct 91 ms 44604 KB Output is correct
8 Correct 95 ms 44612 KB Output is correct
9 Correct 94 ms 44560 KB Output is correct
10 Correct 90 ms 44636 KB Output is correct
11 Correct 108 ms 44584 KB Output is correct
12 Correct 106 ms 44592 KB Output is correct
13 Correct 100 ms 44628 KB Output is correct
14 Correct 91 ms 44656 KB Output is correct
15 Correct 99 ms 44568 KB Output is correct
16 Correct 107 ms 44584 KB Output is correct
17 Correct 90 ms 44656 KB Output is correct
18 Correct 87 ms 44612 KB Output is correct
19 Correct 89 ms 44680 KB Output is correct
20 Correct 98 ms 44624 KB Output is correct
21 Correct 95 ms 44656 KB Output is correct
22 Correct 90 ms 44672 KB Output is correct
23 Correct 97 ms 44636 KB Output is correct
24 Correct 92 ms 44576 KB Output is correct
25 Correct 91 ms 44672 KB Output is correct
26 Correct 93 ms 44684 KB Output is correct
27 Correct 92 ms 44644 KB Output is correct
28 Correct 90 ms 44676 KB Output is correct
29 Correct 91 ms 44620 KB Output is correct
30 Correct 90 ms 44684 KB Output is correct
31 Correct 94 ms 44600 KB Output is correct
32 Correct 89 ms 44696 KB Output is correct
33 Correct 87 ms 44596 KB Output is correct
34 Correct 88 ms 44632 KB Output is correct
35 Correct 87 ms 44668 KB Output is correct
36 Correct 95 ms 44696 KB Output is correct
37 Correct 87 ms 44672 KB Output is correct
38 Correct 91 ms 44676 KB Output is correct
39 Correct 89 ms 44676 KB Output is correct
40 Correct 88 ms 44616 KB Output is correct
41 Correct 90 ms 44576 KB Output is correct
42 Correct 91 ms 44576 KB Output is correct
43 Correct 88 ms 44596 KB Output is correct
44 Correct 89 ms 44596 KB Output is correct
45 Correct 90 ms 44656 KB Output is correct
46 Correct 94 ms 44712 KB Output is correct
47 Correct 92 ms 44616 KB Output is correct
48 Correct 89 ms 44668 KB Output is correct
49 Correct 92 ms 44564 KB Output is correct
50 Correct 111 ms 44664 KB Output is correct
51 Correct 108 ms 44676 KB Output is correct
52 Correct 102 ms 44572 KB Output is correct
53 Correct 92 ms 44680 KB Output is correct
54 Correct 100 ms 44652 KB Output is correct
55 Correct 103 ms 44676 KB Output is correct
56 Correct 93 ms 44680 KB Output is correct
57 Correct 87 ms 44656 KB Output is correct
58 Correct 198 ms 44680 KB Output is correct
59 Correct 301 ms 44732 KB Output is correct
60 Correct 115 ms 44688 KB Output is correct
61 Correct 314 ms 44676 KB Output is correct
62 Correct 110 ms 44712 KB Output is correct
63 Correct 309 ms 44672 KB Output is correct
64 Execution timed out 4083 ms 44676 KB Time limit exceeded
65 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 44660 KB Output is correct
2 Correct 93 ms 44584 KB Output is correct
3 Correct 95 ms 44560 KB Output is correct
4 Correct 86 ms 44676 KB Output is correct
5 Correct 222 ms 70640 KB Output is correct
6 Correct 341 ms 77136 KB Output is correct
7 Correct 170 ms 61116 KB Output is correct
8 Correct 306 ms 77148 KB Output is correct
9 Correct 109 ms 49240 KB Output is correct
10 Correct 322 ms 77132 KB Output is correct
11 Execution timed out 4030 ms 78288 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 44680 KB Output is correct
2 Correct 88 ms 44600 KB Output is correct
3 Correct 88 ms 44676 KB Output is correct
4 Correct 345 ms 59244 KB Output is correct
5 Correct 1054 ms 77128 KB Output is correct
6 Correct 555 ms 49624 KB Output is correct
7 Correct 1087 ms 77100 KB Output is correct
8 Correct 626 ms 55548 KB Output is correct
9 Correct 1058 ms 77180 KB Output is correct
10 Correct 1125 ms 78324 KB Output is correct
11 Correct 953 ms 78140 KB Output is correct
12 Correct 1037 ms 78112 KB Output is correct
13 Correct 939 ms 77248 KB Output is correct
14 Correct 1008 ms 77624 KB Output is correct
15 Correct 911 ms 78272 KB Output is correct
16 Correct 896 ms 78300 KB Output is correct
17 Correct 87 ms 44564 KB Output is correct
18 Correct 87 ms 44572 KB Output is correct
19 Correct 90 ms 44636 KB Output is correct
20 Correct 91 ms 44676 KB Output is correct
21 Correct 92 ms 44596 KB Output is correct
22 Correct 91 ms 44696 KB Output is correct
23 Correct 89 ms 44676 KB Output is correct
24 Correct 89 ms 44660 KB Output is correct
25 Correct 93 ms 44640 KB Output is correct
26 Correct 96 ms 44660 KB Output is correct
27 Correct 116 ms 44708 KB Output is correct
28 Correct 118 ms 44676 KB Output is correct
29 Correct 113 ms 44728 KB Output is correct
30 Correct 109 ms 44676 KB Output is correct
31 Correct 107 ms 44676 KB Output is correct
32 Correct 92 ms 44612 KB Output is correct
33 Correct 206 ms 63368 KB Output is correct
34 Correct 269 ms 77120 KB Output is correct
35 Correct 185 ms 78136 KB Output is correct
36 Correct 255 ms 77148 KB Output is correct
37 Correct 191 ms 77448 KB Output is correct
38 Correct 170 ms 78252 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 44680 KB Output is correct
2 Correct 88 ms 44600 KB Output is correct
3 Correct 88 ms 44676 KB Output is correct
4 Correct 345 ms 59244 KB Output is correct
5 Correct 1054 ms 77128 KB Output is correct
6 Correct 555 ms 49624 KB Output is correct
7 Correct 1087 ms 77100 KB Output is correct
8 Correct 626 ms 55548 KB Output is correct
9 Correct 1058 ms 77180 KB Output is correct
10 Correct 1125 ms 78324 KB Output is correct
11 Correct 953 ms 78140 KB Output is correct
12 Correct 1037 ms 78112 KB Output is correct
13 Correct 939 ms 77248 KB Output is correct
14 Correct 1008 ms 77624 KB Output is correct
15 Correct 911 ms 78272 KB Output is correct
16 Correct 896 ms 78300 KB Output is correct
17 Correct 87 ms 44564 KB Output is correct
18 Correct 87 ms 44572 KB Output is correct
19 Correct 90 ms 44636 KB Output is correct
20 Correct 91 ms 44676 KB Output is correct
21 Correct 92 ms 44596 KB Output is correct
22 Correct 91 ms 44696 KB Output is correct
23 Correct 89 ms 44676 KB Output is correct
24 Correct 89 ms 44660 KB Output is correct
25 Correct 93 ms 44640 KB Output is correct
26 Correct 96 ms 44660 KB Output is correct
27 Correct 116 ms 44708 KB Output is correct
28 Correct 118 ms 44676 KB Output is correct
29 Correct 113 ms 44728 KB Output is correct
30 Correct 109 ms 44676 KB Output is correct
31 Correct 107 ms 44676 KB Output is correct
32 Correct 92 ms 44612 KB Output is correct
33 Correct 206 ms 63368 KB Output is correct
34 Correct 269 ms 77120 KB Output is correct
35 Correct 185 ms 78136 KB Output is correct
36 Correct 255 ms 77148 KB Output is correct
37 Correct 191 ms 77448 KB Output is correct
38 Correct 170 ms 78252 KB Output is correct
39 Correct 91 ms 44676 KB Output is correct
40 Correct 93 ms 44592 KB Output is correct
41 Correct 94 ms 44604 KB Output is correct
42 Correct 350 ms 59212 KB Output is correct
43 Correct 1079 ms 77056 KB Output is correct
44 Correct 685 ms 49716 KB Output is correct
45 Correct 1004 ms 77116 KB Output is correct
46 Correct 615 ms 55512 KB Output is correct
47 Correct 1008 ms 77260 KB Output is correct
48 Correct 1111 ms 78192 KB Output is correct
49 Correct 883 ms 78224 KB Output is correct
50 Correct 936 ms 78148 KB Output is correct
51 Correct 1025 ms 77180 KB Output is correct
52 Correct 1085 ms 77548 KB Output is correct
53 Correct 898 ms 78276 KB Output is correct
54 Correct 882 ms 78208 KB Output is correct
55 Correct 97 ms 44608 KB Output is correct
56 Correct 314 ms 76976 KB Output is correct
57 Correct 890 ms 77028 KB Output is correct
58 Correct 583 ms 50044 KB Output is correct
59 Correct 1086 ms 77148 KB Output is correct
60 Correct 521 ms 55928 KB Output is correct
61 Correct 1114 ms 77056 KB Output is correct
62 Execution timed out 4099 ms 78208 KB Time limit exceeded
63 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 44676 KB Output is correct
2 Correct 96 ms 44672 KB Output is correct
3 Execution timed out 4056 ms 71424 KB Time limit exceeded
4 Halted 0 ms 0 KB -