oj.uz

Submission #587787

# Submission time Handle Problem Language Result Execution time Memory
587787 2022-07-02T11:17:33 Z M_W Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1119 ms 48064 KB 
#include <bits/stdc++.h>
using namespace std;
int dist[200002];
int l[200002], r[200002];
vector<pair<int, int>> v;
int N; bool st1 = true;
int up[200002][21], dis[200002][21];
vector<int> H;

void init(int N_tmp, vector<int> H_tmp) {
	N = N_tmp; H = H_tmp;
	for(int i = 0; i < N; i++){
		v.push_back({H[i], i + 1});
		if(H[i] != i + 1) st1 = false;
	}
	sort(v.begin(), v.end(), greater<pair<int, int>>());
	set<pair<int, int>> v2;
	for(auto [x, tmp] : v){
		if(v2.empty()){
			v2.insert({tmp, x});
			continue;
		}
		auto it = v2.lower_bound({tmp, 0});
		// printf(">> %d %d : %d %d\n", x, tmp, (*it).first, (*it).second);
		if(it != v2.end()) r[x] = (*it).second;
		if(it != v2.begin()){
			it--;
			l[x] = (*it).second;
		}
		
		if((r[x] == 0 && l[x] != 0) || (l[x] < r[x] && l[x] != 0)) up[x][0] = l[x];
		else if(l[x] == 0 || r[x] < l[x]) up[x][0] = r[x];
		dis[x][0] = 1;
		
		int i = 1;
		if(l[x] != 0 && r[x] != 0){
			up[x][1] = max(l[x], r[x]);
			dis[x][1] = 1; i++;
		}
		
		// printf("!!! %d : %d %d: %d %d\n", x, l[x], r[x], up[x][0], up[x][1]);
		
		for(; i <= 20; i++){
			up[x][i] = up[up[x][i - 1]][i - 1];
			dis[x][i] = dis[up[x][i - 1]][i - 1] + dis[x][i - 1];
		}
		
		v2.insert({tmp, x});
	}
//	for(int i = 1; i <= N; i++){
//		for(int j = 0; j <= 3; j++){
//			printf("up %d %d: %d\n", i, j, up[j][i]);
//		}
//	}
}

int minimum_jumps(int A, int B, int C, int D) {
	if(st1) return C - B;
	
	if(A == B && C == D){
		B = H[B], C = H[C];
		int ans = 0;
		for(int i = 20; i >= 0; i--){
			if(up[B][i] != 0 && up[B][i] < C){
				// printf("%d ==> %d, %d\n", B, up[B][i], C);
				ans += dis[B][i];
				B = up[B][i];
			}
		}
		// printf(">> %d %d\n", up[B][0], B);
		if(up[B][0] != C) return -1;
		return ans + dis[B][0];
	}
	
	int ans = 1000000000; A++; B++; C++; D++;
	for(int i = 0; i <= N; i++) dist[i] = 1000000000;
	for(auto [x, idx]: v){
		if(idx >= C && idx <= D) dist[x] = 0;
		if(idx >= A && idx <= B) ans = min({ans, dist[l[x]] + 1, dist[r[x]] + 1});
		
		dist[x] = min({dist[x], dist[l[x]] + 1, dist[r[x]] + 1});
		// printf(">> %d (%d, %d) : %d %d\n", x, l[x], r[x], dist[l[x]], dist[r[x]]);
	}
	return ans == 1000000000 ? -1 : ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 170 ms 37612 KB Output is correct
4 Correct 1065 ms 47148 KB Output is correct
5 Correct 798 ms 23880 KB Output is correct
6 Correct 1119 ms 47268 KB Output is correct
7 Correct 870 ms 32324 KB Output is correct
8 Correct 1018 ms 47260 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 3 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 3 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 184 ms 38652 KB Output is correct
6 Correct 230 ms 48020 KB Output is correct
7 Correct 106 ms 24856 KB Output is correct
8 Correct 288 ms 47988 KB Output is correct
9 Correct 24 ms 7432 KB Output is correct
10 Correct 268 ms 48012 KB Output is correct
11 Correct 149 ms 47220 KB Output is correct
12 Correct 145 ms 47736 KB Output is correct
13 Correct 122 ms 47500 KB Output is correct
14 Correct 182 ms 48064 KB Output is correct
15 Correct 148 ms 48008 KB Output is correct
16 Correct 125 ms 48032 KB Output is correct
17 Correct 123 ms 48040 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 556 KB Output is correct
27 Correct 2 ms 720 KB Output is correct
28 Correct 2 ms 812 KB Output is correct
29 Correct 2 ms 812 KB Output is correct
30 Correct 2 ms 808 KB Output is correct
31 Correct 1 ms 720 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 226 ms 47904 KB Output is correct
34 Correct 236 ms 48048 KB Output is correct
35 Correct 184 ms 47460 KB Output is correct
36 Correct 206 ms 48044 KB Output is correct
37 Correct 184 ms 48048 KB Output is correct
38 Correct 133 ms 47412 KB Output is correct
39 Correct 1 ms 208 KB Output is correct
40 Correct 107 ms 27928 KB Output is correct
41 Correct 267 ms 48028 KB Output is correct
42 Correct 142 ms 47380 KB Output is correct
43 Correct 213 ms 48016 KB Output is correct
44 Correct 143 ms 47948 KB Output is correct
45 Incorrect 149 ms 47468 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Incorrect 308 ms 22152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Incorrect 308 ms 22152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 170 ms 37612 KB Output is correct
4 Correct 1065 ms 47148 KB Output is correct
5 Correct 798 ms 23880 KB Output is correct
6 Correct 1119 ms 47268 KB Output is correct
7 Correct 870 ms 32324 KB Output is correct
8 Correct 1018 ms 47260 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Incorrect 3 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -