oj.uz

Submission #567333

# Submission time Handle Problem Language Result Execution time Memory
567333 2022-05-23T10:38:19 Z amunduzbaev Rainforest Jumps (APIO21_jumps) C++17
65 / 100
 4000 ms 473096 KB 
#include "jumps.h"

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

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

const int B = 1000;
const int N = 2e5 + 5;
const int lg = 18;
vector<int> edges[N];
int mx[N][lg], mn[N][lg], h[N], pos[N];
int st[N][lg], pre[N];
int lx[N], rx[N];

struct ST{
	int tree[N << 2], b;
	void build(int lx = 0, int rx = N - 1, int x = 1){
		if(lx == rx) { tree[x] = pre[lx]; return; }
		int m = (lx + rx) >> 1;
		build(lx, m, x << 1);
		build(m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x<<1], tree[x<<1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N - 1, int x = 1){
		if(lx > r || rx < l) return N;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree[N/B];

void init(int n, vector<int> H){
	for(int i=0;i<n;i++){
		h[i] = H[i];
		pos[h[i]] = i;
		st[i][0] = h[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;
	
	for(int i=0;i<n;i++){
		if(h[lx[i]] < h[rx[i]]){
			swap(lx[i], rx[i]);
		} 
		edges[lx[i]].push_back(i);
		edges[rx[i]].push_back(i);
		mn[i][0] = rx[i];
		mx[i][0] = lx[i];
		lx[i] = min(lx[i], rx[i]);
		if(i < lx[i]) lx[i] = -1;
	}
	mn[n][0] = mx[n][0] = n;
	edges[n].clear();
	
	for(int b=0;b<n/B;b++){
		memset(pre, 127, sizeof pre);
		queue<int> q;
		for(int i=0;b * B + i<n;i++){
			q.push(b * B + i);
			pre[b * B + i] = 0;
		}
		
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(auto x : edges[u]){
				if(pre[x] > pre[u] + 1){
					pre[x] = pre[u] + 1;
					q.push(x);
				}
			}
		}
		
		tree[b].build();
	}
	
	for(int j=1;j<lg;j++){
		for(int i=0;i<=n;i++){
			if(i + (1 << (j - 1)) < n) st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j-1]);
			mn[i][j] = mn[mn[i][j-1]][j-1];
			mx[i][j] = mx[mx[i][j-1]][j-1];
		}
	}
}

int get(int l, int r){
	int lg = __lg(r - l + 1);
	return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
}

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 bl = c / B, br = d / B;
	int res = N;
	for(int j=bl+1;j<br;j++){
		//~ assert(false);
		res = min(res, tree[j].get(a, b));
	}
	
	auto calc = [&](int l, int r){
		for(int i=l;i<=r;i++){
			int L = max(lx[i] + 1, a);
			if(L <= b){
				int mx = pos[get(L, b)];
				res = min(res, check(mx, i));
			}
		}
	};
	
	if(bl == br){
		calc(c, d);
	} else {
		if(c % B == 0) res = min(res, tree[bl].get(a, b));
		else calc(c, (bl + 1) * B - 1);
		if((d + 1) % B == 0) res = min(res, tree[br].get(a, b));
		else calc(br * B, d);
	}
	
	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 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 1851 ms 377308 KB Output is correct
4 Execution timed out 4041 ms 473088 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 4944 KB Output is correct
6 Correct 5 ms 5084 KB Output is correct
7 Correct 5 ms 5072 KB Output is correct
8 Correct 5 ms 5072 KB Output is correct
9 Correct 4 ms 5072 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 7 ms 5072 KB Output is correct
12 Correct 6 ms 5072 KB Output is correct
13 Correct 5 ms 5072 KB Output is correct
14 Correct 6 ms 5072 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 5 ms 5072 KB Output is correct
18 Correct 3 ms 4944 KB Output is correct
19 Correct 3 ms 4944 KB Output is correct
20 Correct 5 ms 5072 KB Output is correct
21 Correct 6 ms 5072 KB Output is correct
22 Correct 5 ms 5072 KB Output is correct
23 Correct 5 ms 5072 KB Output is correct
24 Correct 5 ms 5072 KB Output is correct
25 Correct 3 ms 4944 KB Output is correct
26 Correct 3 ms 4944 KB Output is correct
27 Correct 4 ms 4944 KB Output is correct
28 Correct 5 ms 5072 KB Output is correct
29 Correct 5 ms 5072 KB Output is correct
30 Correct 5 ms 5072 KB Output is correct
31 Correct 5 ms 5072 KB Output is correct
32 Correct 5 ms 5072 KB Output is correct
33 Correct 4 ms 4944 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5072 KB Output is correct
36 Correct 3 ms 5120 KB Output is correct
37 Correct 3 ms 5036 KB Output is correct
38 Correct 4 ms 5072 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 4944 KB Output is correct
6 Correct 5 ms 5084 KB Output is correct
7 Correct 5 ms 5072 KB Output is correct
8 Correct 5 ms 5072 KB Output is correct
9 Correct 4 ms 5072 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 7 ms 5072 KB Output is correct
12 Correct 6 ms 5072 KB Output is correct
13 Correct 5 ms 5072 KB Output is correct
14 Correct 6 ms 5072 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 5 ms 5072 KB Output is correct
18 Correct 3 ms 4944 KB Output is correct
19 Correct 3 ms 4944 KB Output is correct
20 Correct 5 ms 5072 KB Output is correct
21 Correct 6 ms 5072 KB Output is correct
22 Correct 5 ms 5072 KB Output is correct
23 Correct 5 ms 5072 KB Output is correct
24 Correct 5 ms 5072 KB Output is correct
25 Correct 3 ms 4944 KB Output is correct
26 Correct 3 ms 4944 KB Output is correct
27 Correct 4 ms 4944 KB Output is correct
28 Correct 5 ms 5072 KB Output is correct
29 Correct 5 ms 5072 KB Output is correct
30 Correct 5 ms 5072 KB Output is correct
31 Correct 5 ms 5072 KB Output is correct
32 Correct 5 ms 5072 KB Output is correct
33 Correct 4 ms 4944 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5072 KB Output is correct
36 Correct 3 ms 5120 KB Output is correct
37 Correct 3 ms 5036 KB Output is correct
38 Correct 4 ms 5072 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 3 ms 4944 KB Output is correct
41 Correct 3 ms 4944 KB Output is correct
42 Correct 3 ms 4944 KB Output is correct
43 Correct 3 ms 4944 KB Output is correct
44 Correct 4 ms 4944 KB Output is correct
45 Correct 6 ms 5072 KB Output is correct
46 Correct 5 ms 5072 KB Output is correct
47 Correct 5 ms 5120 KB Output is correct
48 Correct 3 ms 5072 KB Output is correct
49 Correct 5 ms 5072 KB Output is correct
50 Correct 6 ms 5128 KB Output is correct
51 Correct 4 ms 5072 KB Output is correct
52 Correct 6 ms 5072 KB Output is correct
53 Correct 5 ms 5072 KB Output is correct
54 Correct 5 ms 5072 KB Output is correct
55 Correct 7 ms 5072 KB Output is correct
56 Correct 5 ms 5072 KB Output is correct
57 Correct 3 ms 5072 KB Output is correct
58 Correct 22 ms 8272 KB Output is correct
59 Correct 26 ms 10372 KB Output is correct
60 Correct 11 ms 5200 KB Output is correct
61 Correct 27 ms 10448 KB Output is correct
62 Correct 16 ms 5076 KB Output is correct
63 Correct 28 ms 10448 KB Output is correct
64 Correct 82 ms 10428 KB Output is correct
65 Correct 75 ms 10444 KB Output is correct
66 Correct 67 ms 10448 KB Output is correct
67 Correct 30 ms 10448 KB Output is correct
68 Correct 46 ms 10448 KB Output is correct
69 Correct 31 ms 10448 KB Output is correct
70 Correct 79 ms 10448 KB Output is correct
71 Correct 4 ms 4944 KB Output is correct
72 Correct 3 ms 4944 KB Output is correct
73 Correct 4 ms 5072 KB Output is correct
74 Correct 5 ms 5072 KB Output is correct
75 Correct 6 ms 5084 KB Output is correct
76 Correct 6 ms 5072 KB Output is correct
77 Correct 5 ms 5072 KB Output is correct
78 Correct 4 ms 4944 KB Output is correct
79 Correct 3 ms 4944 KB Output is correct
80 Correct 3 ms 4944 KB Output is correct
81 Correct 6 ms 5072 KB Output is correct
82 Correct 6 ms 5072 KB Output is correct
83 Correct 5 ms 5072 KB Output is correct
84 Correct 4 ms 5072 KB Output is correct
85 Correct 5 ms 5072 KB Output is correct
86 Correct 3 ms 4944 KB Output is correct
87 Correct 3 ms 5072 KB Output is correct
88 Correct 5 ms 5072 KB Output is correct
89 Correct 3 ms 5072 KB Output is correct
90 Correct 3 ms 5072 KB Output is correct
91 Correct 3 ms 5072 KB Output is correct
92 Correct 3 ms 5072 KB Output is correct
93 Correct 3 ms 5072 KB Output is correct
94 Correct 5 ms 5120 KB Output is correct
95 Correct 28 ms 10448 KB Output is correct
96 Correct 23 ms 10448 KB Output is correct
97 Correct 24 ms 10448 KB Output is correct
98 Correct 23 ms 10448 KB Output is correct
99 Correct 20 ms 10448 KB Output is correct
100 Correct 3 ms 5072 KB Output is correct
101 Correct 5 ms 5200 KB Output is correct
102 Correct 22 ms 10448 KB Output is correct
103 Correct 20 ms 10448 KB Output is correct
104 Correct 23 ms 10408 KB Output is correct
105 Correct 24 ms 10448 KB Output is correct
106 Correct 16 ms 10384 KB Output is correct
107 Correct 4 ms 5012 KB Output is correct
108 Correct 3 ms 5200 KB Output is correct
109 Correct 8 ms 10372 KB Output is correct
110 Correct 7 ms 10448 KB Output is correct
111 Correct 7 ms 10448 KB Output is correct
112 Correct 9 ms 10448 KB Output is correct
113 Correct 7 ms 10376 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 869 ms 377092 KB Output is correct
6 Correct 965 ms 469184 KB Output is correct
7 Correct 328 ms 242524 KB Output is correct
8 Incorrect 1304 ms 469684 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 498 ms 216976 KB Output is correct
5 Correct 1739 ms 469252 KB Output is correct
6 Correct 684 ms 80252 KB Output is correct
7 Correct 1791 ms 469652 KB Output is correct
8 Correct 716 ms 163720 KB Output is correct
9 Correct 1591 ms 469244 KB Output is correct
10 Correct 1682 ms 472952 KB Output is correct
11 Correct 1855 ms 472964 KB Output is correct
12 Correct 1587 ms 472916 KB Output is correct
13 Correct 1588 ms 470012 KB Output is correct
14 Correct 1915 ms 471824 KB Output is correct
15 Correct 1467 ms 473024 KB Output is correct
16 Correct 1537 ms 472912 KB Output is correct
17 Correct 3 ms 4944 KB Output is correct
18 Correct 5 ms 4944 KB Output is correct
19 Correct 4 ms 4944 KB Output is correct
20 Correct 5 ms 5072 KB Output is correct
21 Correct 5 ms 5072 KB Output is correct
22 Correct 5 ms 5072 KB Output is correct
23 Correct 5 ms 5072 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 5 ms 5200 KB Output is correct
27 Correct 26 ms 10448 KB Output is correct
28 Correct 25 ms 10448 KB Output is correct
29 Correct 20 ms 10376 KB Output is correct
30 Correct 15 ms 10448 KB Output is correct
31 Correct 25 ms 10448 KB Output is correct
32 Correct 3 ms 4944 KB Output is correct
33 Correct 471 ms 272524 KB Output is correct
34 Correct 997 ms 469756 KB Output is correct
35 Correct 903 ms 472912 KB Output is correct
36 Correct 1351 ms 469456 KB Output is correct
37 Correct 781 ms 471796 KB Output is correct
38 Correct 649 ms 472964 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 498 ms 216976 KB Output is correct
5 Correct 1739 ms 469252 KB Output is correct
6 Correct 684 ms 80252 KB Output is correct
7 Correct 1791 ms 469652 KB Output is correct
8 Correct 716 ms 163720 KB Output is correct
9 Correct 1591 ms 469244 KB Output is correct
10 Correct 1682 ms 472952 KB Output is correct
11 Correct 1855 ms 472964 KB Output is correct
12 Correct 1587 ms 472916 KB Output is correct
13 Correct 1588 ms 470012 KB Output is correct
14 Correct 1915 ms 471824 KB Output is correct
15 Correct 1467 ms 473024 KB Output is correct
16 Correct 1537 ms 472912 KB Output is correct
17 Correct 3 ms 4944 KB Output is correct
18 Correct 5 ms 4944 KB Output is correct
19 Correct 4 ms 4944 KB Output is correct
20 Correct 5 ms 5072 KB Output is correct
21 Correct 5 ms 5072 KB Output is correct
22 Correct 5 ms 5072 KB Output is correct
23 Correct 5 ms 5072 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 5 ms 5200 KB Output is correct
27 Correct 26 ms 10448 KB Output is correct
28 Correct 25 ms 10448 KB Output is correct
29 Correct 20 ms 10376 KB Output is correct
30 Correct 15 ms 10448 KB Output is correct
31 Correct 25 ms 10448 KB Output is correct
32 Correct 3 ms 4944 KB Output is correct
33 Correct 471 ms 272524 KB Output is correct
34 Correct 997 ms 469756 KB Output is correct
35 Correct 903 ms 472912 KB Output is correct
36 Correct 1351 ms 469456 KB Output is correct
37 Correct 781 ms 471796 KB Output is correct
38 Correct 649 ms 472964 KB Output is correct
39 Correct 4 ms 4964 KB Output is correct
40 Correct 3 ms 4944 KB Output is correct
41 Correct 4 ms 4944 KB Output is correct
42 Correct 574 ms 216824 KB Output is correct
43 Correct 2140 ms 469216 KB Output is correct
44 Correct 540 ms 80252 KB Output is correct
45 Correct 1810 ms 469668 KB Output is correct
46 Correct 780 ms 163684 KB Output is correct
47 Correct 1940 ms 469216 KB Output is correct
48 Correct 1822 ms 472992 KB Output is correct
49 Correct 1748 ms 472972 KB Output is correct
50 Correct 1634 ms 472828 KB Output is correct
51 Correct 1744 ms 469972 KB Output is correct
52 Correct 1692 ms 471948 KB Output is correct
53 Correct 1264 ms 473096 KB Output is correct
54 Correct 1320 ms 473032 KB Output is correct
55 Correct 3 ms 4944 KB Output is correct
56 Correct 1138 ms 467468 KB Output is correct
57 Correct 1862 ms 469620 KB Output is correct
58 Correct 478 ms 86948 KB Output is correct
59 Correct 1871 ms 469616 KB Output is correct
60 Correct 638 ms 170480 KB Output is correct
61 Correct 2123 ms 469152 KB Output is correct
62 Correct 1907 ms 472976 KB Output is correct
63 Correct 1579 ms 472788 KB Output is correct
64 Correct 1949 ms 472272 KB Output is correct
65 Correct 2066 ms 469436 KB Output is correct
66 Correct 1950 ms 471740 KB Output is correct
67 Correct 1520 ms 472908 KB Output is correct
68 Correct 1279 ms 472924 KB Output is correct
69 Correct 3 ms 4992 KB Output is correct
70 Correct 4 ms 4964 KB Output is correct
71 Correct 7 ms 5120 KB Output is correct
72 Correct 6 ms 5072 KB Output is correct
73 Correct 7 ms 5072 KB Output is correct
74 Correct 6 ms 5072 KB Output is correct
75 Correct 5 ms 5036 KB Output is correct
76 Correct 3 ms 4944 KB Output is correct
77 Correct 3 ms 4944 KB Output is correct
78 Correct 4 ms 4944 KB Output is correct
79 Correct 7 ms 5072 KB Output is correct
80 Correct 4 ms 5072 KB Output is correct
81 Correct 6 ms 5072 KB Output is correct
82 Correct 7 ms 5072 KB Output is correct
83 Correct 7 ms 5072 KB Output is correct
84 Correct 3 ms 5072 KB Output is correct
85 Correct 9 ms 5072 KB Output is correct
86 Correct 19 ms 10460 KB Output is correct
87 Correct 29 ms 10448 KB Output is correct
88 Correct 25 ms 10448 KB Output is correct
89 Correct 26 ms 10448 KB Output is correct
90 Correct 30 ms 10496 KB Output is correct
91 Correct 3 ms 5072 KB Output is correct
92 Correct 4 ms 5248 KB Output is correct
93 Correct 30 ms 10448 KB Output is correct
94 Correct 31 ms 10448 KB Output is correct
95 Correct 27 ms 10484 KB Output is correct
96 Correct 35 ms 10468 KB Output is correct
97 Correct 20 ms 10496 KB Output is correct
98 Correct 3 ms 4944 KB Output is correct
99 Correct 1301 ms 467592 KB Output is correct
100 Correct 1035 ms 469784 KB Output is correct
101 Correct 834 ms 472840 KB Output is correct
102 Correct 1186 ms 470120 KB Output is correct
103 Correct 849 ms 471832 KB Output is correct
104 Correct 618 ms 473020 KB Output is correct
105 Correct 3 ms 4944 KB Output is correct
106 Correct 441 ms 272548 KB Output is correct
107 Correct 939 ms 469676 KB Output is correct
108 Correct 774 ms 472904 KB Output is correct
109 Correct 1325 ms 469504 KB Output is correct
110 Correct 797 ms 471772 KB Output is correct
111 Correct 637 ms 473020 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 1851 ms 377308 KB Output is correct
4 Execution timed out 4041 ms 473088 KB Time limit exceeded
5 Halted 0 ms 0 KB -