oj.uz

Submission #566876

# Submission time Handle Problem Language Result Execution time Memory
566876 2022-05-23T05:02:47 Z amunduzbaev Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1591 ms 78460 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 v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			auto it = lower_bound(tree[x].begin(), tree[x].end(), v);
			if(it == tree[x].begin()) return -1;
			return *--it;
		} int m = (lx + rx) >> 1;
		return max(get(l, r, v, lx, m, x<<1), get(l, r, v, 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 -1;
	return res;
}

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

/*

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

*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 44580 KB Output is correct
2 Correct 94 ms 44636 KB Output is correct
3 Correct 316 ms 71404 KB Output is correct
4 Correct 1591 ms 78224 KB Output is correct
5 Correct 1325 ms 61188 KB Output is correct
6 Correct 1385 ms 78220 KB Output is correct
7 Correct 1199 ms 67572 KB Output is correct
8 Correct 1321 ms 78300 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 44608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 44608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 44608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 44676 KB Output is correct
2 Correct 128 ms 44688 KB Output is correct
3 Correct 133 ms 44672 KB Output is correct
4 Correct 409 ms 59224 KB Output is correct
5 Correct 1191 ms 77168 KB Output is correct
6 Correct 719 ms 49612 KB Output is correct
7 Correct 1066 ms 77104 KB Output is correct
8 Correct 684 ms 55564 KB Output is correct
9 Correct 1086 ms 77152 KB Output is correct
10 Correct 1130 ms 78308 KB Output is correct
11 Correct 976 ms 78240 KB Output is correct
12 Correct 988 ms 78148 KB Output is correct
13 Correct 1072 ms 77244 KB Output is correct
14 Correct 1040 ms 77548 KB Output is correct
15 Correct 966 ms 78288 KB Output is correct
16 Correct 1034 ms 78236 KB Output is correct
17 Correct 92 ms 44708 KB Output is correct
18 Correct 96 ms 44652 KB Output is correct
19 Correct 95 ms 44664 KB Output is correct
20 Correct 104 ms 44680 KB Output is correct
21 Correct 100 ms 44688 KB Output is correct
22 Correct 93 ms 44676 KB Output is correct
23 Correct 105 ms 44604 KB Output is correct
24 Correct 104 ms 44628 KB Output is correct
25 Correct 105 ms 44600 KB Output is correct
26 Correct 91 ms 44680 KB Output is correct
27 Correct 115 ms 44740 KB Output is correct
28 Correct 116 ms 44672 KB Output is correct
29 Correct 113 ms 44648 KB Output is correct
30 Correct 105 ms 44672 KB Output is correct
31 Correct 110 ms 44760 KB Output is correct
32 Correct 101 ms 44572 KB Output is correct
33 Correct 221 ms 63340 KB Output is correct
34 Correct 263 ms 77100 KB Output is correct
35 Correct 164 ms 78156 KB Output is correct
36 Correct 278 ms 77120 KB Output is correct
37 Correct 204 ms 77468 KB Output is correct
38 Correct 179 ms 78460 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 44676 KB Output is correct
2 Correct 128 ms 44688 KB Output is correct
3 Correct 133 ms 44672 KB Output is correct
4 Correct 409 ms 59224 KB Output is correct
5 Correct 1191 ms 77168 KB Output is correct
6 Correct 719 ms 49612 KB Output is correct
7 Correct 1066 ms 77104 KB Output is correct
8 Correct 684 ms 55564 KB Output is correct
9 Correct 1086 ms 77152 KB Output is correct
10 Correct 1130 ms 78308 KB Output is correct
11 Correct 976 ms 78240 KB Output is correct
12 Correct 988 ms 78148 KB Output is correct
13 Correct 1072 ms 77244 KB Output is correct
14 Correct 1040 ms 77548 KB Output is correct
15 Correct 966 ms 78288 KB Output is correct
16 Correct 1034 ms 78236 KB Output is correct
17 Correct 92 ms 44708 KB Output is correct
18 Correct 96 ms 44652 KB Output is correct
19 Correct 95 ms 44664 KB Output is correct
20 Correct 104 ms 44680 KB Output is correct
21 Correct 100 ms 44688 KB Output is correct
22 Correct 93 ms 44676 KB Output is correct
23 Correct 105 ms 44604 KB Output is correct
24 Correct 104 ms 44628 KB Output is correct
25 Correct 105 ms 44600 KB Output is correct
26 Correct 91 ms 44680 KB Output is correct
27 Correct 115 ms 44740 KB Output is correct
28 Correct 116 ms 44672 KB Output is correct
29 Correct 113 ms 44648 KB Output is correct
30 Correct 105 ms 44672 KB Output is correct
31 Correct 110 ms 44760 KB Output is correct
32 Correct 101 ms 44572 KB Output is correct
33 Correct 221 ms 63340 KB Output is correct
34 Correct 263 ms 77100 KB Output is correct
35 Correct 164 ms 78156 KB Output is correct
36 Correct 278 ms 77120 KB Output is correct
37 Correct 204 ms 77468 KB Output is correct
38 Correct 179 ms 78460 KB Output is correct
39 Correct 105 ms 44664 KB Output is correct
40 Correct 106 ms 44584 KB Output is correct
41 Correct 92 ms 44596 KB Output is correct
42 Correct 384 ms 59304 KB Output is correct
43 Correct 1065 ms 77244 KB Output is correct
44 Correct 515 ms 49660 KB Output is correct
45 Correct 998 ms 77148 KB Output is correct
46 Correct 545 ms 55528 KB Output is correct
47 Correct 984 ms 77112 KB Output is correct
48 Correct 1155 ms 78220 KB Output is correct
49 Correct 1029 ms 78140 KB Output is correct
50 Correct 1087 ms 78140 KB Output is correct
51 Correct 1108 ms 77052 KB Output is correct
52 Correct 1081 ms 77540 KB Output is correct
53 Correct 997 ms 78308 KB Output is correct
54 Correct 786 ms 78220 KB Output is correct
55 Correct 92 ms 44696 KB Output is correct
56 Incorrect 322 ms 76968 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 44580 KB Output is correct
2 Correct 94 ms 44636 KB Output is correct
3 Correct 316 ms 71404 KB Output is correct
4 Correct 1591 ms 78224 KB Output is correct
5 Correct 1325 ms 61188 KB Output is correct
6 Correct 1385 ms 78220 KB Output is correct
7 Correct 1199 ms 67572 KB Output is correct
8 Correct 1321 ms 78300 KB Output is correct
9 Incorrect 105 ms 44608 KB Output isn't correct
10 Halted 0 ms 0 KB -