oj.uz

Submission #566902

# Submission time Handle Problem Language Result Execution time Memory
566902 2022-05-23T05:50:28 Z amunduzbaev Rainforest Jumps (APIO21_jumps) C++17
23 / 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 L = max(a, tree.get_(a, b, h[i]) + 1);
		if(L > b) continue;
		int mx = b;
		for(int j=b;j>=L;j--){
			if(h[j] > h[mx]) mx = j;
		}
		res = min(res, check(mx, 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 90 ms 44644 KB Output is correct
2 Correct 92 ms 44664 KB Output is correct
3 Execution timed out 4064 ms 71400 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 44684 KB Output is correct
2 Correct 91 ms 44588 KB Output is correct
3 Correct 89 ms 44564 KB Output is correct
4 Correct 91 ms 44584 KB Output is correct
5 Incorrect 92 ms 44572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 44684 KB Output is correct
2 Correct 91 ms 44588 KB Output is correct
3 Correct 89 ms 44564 KB Output is correct
4 Correct 91 ms 44584 KB Output is correct
5 Incorrect 92 ms 44572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 44676 KB Output is correct
2 Correct 94 ms 44644 KB Output is correct
3 Correct 98 ms 44692 KB Output is correct
4 Correct 89 ms 44672 KB Output is correct
5 Correct 1061 ms 70716 KB Output is correct
6 Execution timed out 4073 ms 77136 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 44648 KB Output is correct
2 Correct 89 ms 44616 KB Output is correct
3 Correct 89 ms 44680 KB Output is correct
4 Correct 369 ms 59260 KB Output is correct
5 Correct 931 ms 77188 KB Output is correct
6 Correct 660 ms 49700 KB Output is correct
7 Correct 1066 ms 77052 KB Output is correct
8 Correct 606 ms 55612 KB Output is correct
9 Correct 1106 ms 77220 KB Output is correct
10 Correct 962 ms 78204 KB Output is correct
11 Correct 995 ms 78188 KB Output is correct
12 Correct 860 ms 78176 KB Output is correct
13 Correct 943 ms 77228 KB Output is correct
14 Correct 1065 ms 77536 KB Output is correct
15 Correct 830 ms 78200 KB Output is correct
16 Correct 996 ms 78232 KB Output is correct
17 Correct 91 ms 44684 KB Output is correct
18 Correct 90 ms 44564 KB Output is correct
19 Correct 90 ms 44652 KB Output is correct
20 Correct 97 ms 44640 KB Output is correct
21 Correct 92 ms 44716 KB Output is correct
22 Correct 91 ms 44616 KB Output is correct
23 Correct 92 ms 44608 KB Output is correct
24 Correct 92 ms 44584 KB Output is correct
25 Correct 93 ms 44616 KB Output is correct
26 Correct 95 ms 44676 KB Output is correct
27 Correct 108 ms 44688 KB Output is correct
28 Correct 115 ms 44676 KB Output is correct
29 Correct 106 ms 44620 KB Output is correct
30 Correct 113 ms 44672 KB Output is correct
31 Correct 105 ms 44708 KB Output is correct
32 Correct 94 ms 44644 KB Output is correct
33 Correct 186 ms 63228 KB Output is correct
34 Correct 268 ms 77140 KB Output is correct
35 Correct 161 ms 78188 KB Output is correct
36 Correct 239 ms 77064 KB Output is correct
37 Correct 189 ms 77540 KB Output is correct
38 Correct 170 ms 78200 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 44648 KB Output is correct
2 Correct 89 ms 44616 KB Output is correct
3 Correct 89 ms 44680 KB Output is correct
4 Correct 369 ms 59260 KB Output is correct
5 Correct 931 ms 77188 KB Output is correct
6 Correct 660 ms 49700 KB Output is correct
7 Correct 1066 ms 77052 KB Output is correct
8 Correct 606 ms 55612 KB Output is correct
9 Correct 1106 ms 77220 KB Output is correct
10 Correct 962 ms 78204 KB Output is correct
11 Correct 995 ms 78188 KB Output is correct
12 Correct 860 ms 78176 KB Output is correct
13 Correct 943 ms 77228 KB Output is correct
14 Correct 1065 ms 77536 KB Output is correct
15 Correct 830 ms 78200 KB Output is correct
16 Correct 996 ms 78232 KB Output is correct
17 Correct 91 ms 44684 KB Output is correct
18 Correct 90 ms 44564 KB Output is correct
19 Correct 90 ms 44652 KB Output is correct
20 Correct 97 ms 44640 KB Output is correct
21 Correct 92 ms 44716 KB Output is correct
22 Correct 91 ms 44616 KB Output is correct
23 Correct 92 ms 44608 KB Output is correct
24 Correct 92 ms 44584 KB Output is correct
25 Correct 93 ms 44616 KB Output is correct
26 Correct 95 ms 44676 KB Output is correct
27 Correct 108 ms 44688 KB Output is correct
28 Correct 115 ms 44676 KB Output is correct
29 Correct 106 ms 44620 KB Output is correct
30 Correct 113 ms 44672 KB Output is correct
31 Correct 105 ms 44708 KB Output is correct
32 Correct 94 ms 44644 KB Output is correct
33 Correct 186 ms 63228 KB Output is correct
34 Correct 268 ms 77140 KB Output is correct
35 Correct 161 ms 78188 KB Output is correct
36 Correct 239 ms 77064 KB Output is correct
37 Correct 189 ms 77540 KB Output is correct
38 Correct 170 ms 78200 KB Output is correct
39 Correct 90 ms 44620 KB Output is correct
40 Correct 91 ms 44564 KB Output is correct
41 Correct 90 ms 44744 KB Output is correct
42 Correct 386 ms 59320 KB Output is correct
43 Correct 892 ms 77152 KB Output is correct
44 Correct 604 ms 49612 KB Output is correct
45 Correct 1032 ms 77112 KB Output is correct
46 Correct 617 ms 55520 KB Output is correct
47 Correct 1002 ms 77044 KB Output is correct
48 Correct 1057 ms 78324 KB Output is correct
49 Correct 911 ms 78144 KB Output is correct
50 Correct 793 ms 78140 KB Output is correct
51 Correct 996 ms 77108 KB Output is correct
52 Correct 996 ms 77536 KB Output is correct
53 Correct 987 ms 78268 KB Output is correct
54 Correct 966 ms 78268 KB Output is correct
55 Correct 93 ms 44648 KB Output is correct
56 Incorrect 1263 ms 76988 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 44644 KB Output is correct
2 Correct 92 ms 44664 KB Output is correct
3 Execution timed out 4064 ms 71400 KB Time limit exceeded
4 Halted 0 ms 0 KB -