This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;
const int lg = 18, N = 2e5 + 5, inf = 1e9;
vector jump(lg, vector(N, N));
int n;
void init(int N, vector<int> H) {
n = N;
stack<int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() and H[s.top()] < H[i]) s.pop();
jump[0][i] = s.empty() ? n : s.top();
s.push(i);
if (jump[0][i] == n) continue;
for (int j = 1; j < lg; j++) {
jump[j][i] = jump[j - 1][jump[j - 1][i]];
if (jump[j][i] >= n) break;
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
int ans = inf;
for (int i = a; i <= b; i++) {
int x = i, now = 0;
for (int j = lg - 1; j >= 0; j--) {
if (jump[j][x] >= c) continue;
x = jump[j][x];
now += 1 << j;
}
if (c <= jump[0][x] and jump[0][x] <= d) ans = min(ans, now + 1);
}
if (ans == inf) return -1;
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |