#include <bits/stdc++.h>
using namespace std;
const int mxN = 200005;
bool sub1 = false;
vector<int> height;
void init(int n, vector<int> h) {
if(is_sorted(h.begin(), h.end()))
sub1 = true;
height = h;
}
int bfs(int i, int end) {
int n = int(height.size());
queue<pair<int, int> > q;
q.push({i, 0});
while(!q.empty()) {
int u = q.front().first, jumps = q.front().second;
q.pop();
if(u == end)
return jumps;
if(height[u] > height[end]) continue;
int j = u;
while(j >= 0 && height[j] <= height[u])
j--;
// cout << "bfs_1: " << u << " " << j << " " << jumps+1 << "\n";
if(j >= 0)
q.push({j, jumps+1});
j = u;
while(j < n && height[j] <= height[u])
j++;
// cout << "bfs_2: " << u << " " << j << " " << jumps+1 << "\n";
if(j < n)
q.push({j, jumps+1});
}
return -1;
}
int minimum_jumps(int a, int b, int c, int d) {
if(sub1)
return c-b;
else {
int ans = INT_MAX;
for(int i = a; i <= b; i++) {
int pos = i;
for(int j = c; j <= d; j++) {
if(height[j] < height[i]) continue;
int jumps = bfs(pos, j);
// cout << i << " " << j << " " << jumps << "\n";
if(jumps != -1)
ans = min(ans, jumps);
}
}
return ans;
}
}
/*
int main() {
int n = 7;
vector<int> h = {3, 2, 1, 6, 4, 5, 7};
init(n, h);
int a = 1, b = 3, c = 5, d = 6;
printf("%d\n", minimum_jumps(a, b, c, d));
return 0;
}*/
/*
0 1 2 3 4 5 6
3 2 1 6 4 5 7
(1, 3)
(5, 6)
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
98 ms |
2112 KB |
Output is correct |
4 |
Correct |
1244 ms |
2580 KB |
Output is correct |
5 |
Correct |
854 ms |
1452 KB |
Output is correct |
6 |
Correct |
982 ms |
2624 KB |
Output is correct |
7 |
Correct |
864 ms |
1856 KB |
Output is correct |
8 |
Correct |
972 ms |
2604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
98 ms |
2112 KB |
Output is correct |
4 |
Correct |
1244 ms |
2580 KB |
Output is correct |
5 |
Correct |
854 ms |
1452 KB |
Output is correct |
6 |
Correct |
982 ms |
2624 KB |
Output is correct |
7 |
Correct |
864 ms |
1856 KB |
Output is correct |
8 |
Correct |
972 ms |
2604 KB |
Output is correct |
9 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |