#include "jumps.h"
#include <vector>
using namespace std;
#include <bits/stdc++.h>
const int MAXN = 2e5 + 5;
int DP_Min[19][MAXN], DP_Max[19][MAXN];
vector<int> INPUT;
void init(int N, vector<int> H) {
vector<int> L(N), R(N);
stack<int> q;
for(int i = 0; i < N; i++) {
INPUT.push_back(H[i]);
while(!q.empty() && H[q.top()] <= H[i]) {
q.pop();
}
if(q.empty()) {
L[i] = -1;
}
else {
L[i] = q.top();
}
q.push(i);
}
while(!q.empty()) {
q.pop();
}
for(int i = N - 1; i >= 0; i--) {
while(!q.empty() && H[q.top()] <= H[i]) {
q.pop();
}
if(q.empty()) {
R[i] = N;
}
else {
R[i] = q.top();
}
q.push(i);
}
for(int i = 0; i < N; i++) {
if(L[i] == -1 && R[i] == N) {
DP_Min[0][i] = -1;
DP_Max[0][i] = -1;
}
else if(L[i] == -1 || R[i] == N) {
if(L[i] == -1) {
DP_Min[0][i] = R[i];
DP_Max[0][i] = R[i];
}
else {
DP_Min[0][i] = L[i];
DP_Max[0][i] = L[i];
}
}
else {
DP_Min[0][i] = min(L[i], R[i]);
DP_Max[0][i] = max(L[i], R[i]);
}
}
for(int i = 1; i < 19; i++) {
for(int j = 0; j < N; j++) {
if(DP_Min[i - 1][j] == -1) {
DP_Min[i][j] = -1;
}
else {
DP_Min[i][j] = DP_Min[i - 1][DP_Min[i - 1][j]];
}
if(DP_Max[i - 1][j] == -1) {
DP_Max[i][j] = -1;
}
else {
DP_Max[i][j] = DP_Max[i - 1][DP_Max[i - 1][j]];
}
}
}
//cout << "L[i] and R[i]\n";
//for(int i = 0; i < N; i++) {
// cout << L[i] << " " << R[i] << "\n";
//}
//cout << DP_Min[0][4] << " " << DP_Max[0][4] << "\n";
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0, cur = B;
for(int i = 18; i >= 0; i--) {
if(DP_Max[i][cur] != -1 && INPUT[DP_Max[i][cur]] <= INPUT[C]) {
//cout << "prev cur = " << cur << "\n";
ans += (1 << i);
cur = DP_Max[i][cur];
//cout << "new cur = " << cur << ", with added answer: " << (1 << i) << "\n";
}
}
for(int i = 18; i >= 0; i--) {
if(DP_Min[i][cur] != -1 && INPUT[DP_Min[i][cur]] <= INPUT[C]) {
ans += (1 << i);
cur = DP_Min[i][cur];
}
}
if(cur != C) return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
464 KB |
Output is correct |
2 |
Correct |
0 ms |
464 KB |
Output is correct |
3 |
Correct |
130 ms |
27888 KB |
Output is correct |
4 |
Correct |
930 ms |
34708 KB |
Output is correct |
5 |
Correct |
768 ms |
17728 KB |
Output is correct |
6 |
Correct |
974 ms |
34708 KB |
Output is correct |
7 |
Correct |
636 ms |
23956 KB |
Output is correct |
8 |
Correct |
912 ms |
34748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
464 KB |
Output is correct |
2 |
Correct |
0 ms |
464 KB |
Output is correct |
3 |
Correct |
1 ms |
464 KB |
Output is correct |
4 |
Incorrect |
259 ms |
15968 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
464 KB |
Output is correct |
2 |
Correct |
0 ms |
464 KB |
Output is correct |
3 |
Correct |
1 ms |
464 KB |
Output is correct |
4 |
Incorrect |
259 ms |
15968 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
464 KB |
Output is correct |
2 |
Correct |
0 ms |
464 KB |
Output is correct |
3 |
Correct |
130 ms |
27888 KB |
Output is correct |
4 |
Correct |
930 ms |
34708 KB |
Output is correct |
5 |
Correct |
768 ms |
17728 KB |
Output is correct |
6 |
Correct |
974 ms |
34708 KB |
Output is correct |
7 |
Correct |
636 ms |
23956 KB |
Output is correct |
8 |
Correct |
912 ms |
34748 KB |
Output is correct |
9 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |