#include<bits/stdc++.h>
#ifndef LOCAL
#include "jumps.h"
#endif
#define ld long double
#define ll long long
#define pb push_back
using namespace std;
const int INF = 1e9;
mt19937 rnd(51);
int n;
vector<int> h, l, r;
void init(int N, std::vector<int> H) {
h = H;
n = N;
l.resize(n, -1);
r.resize(n, n);
deque<int> q;
for (int i = 0; i < n; i++) {
while (q.size() > 0 && h[q.back()] < h[i]) {
r[q.back()] = i;
q.pop_back();
}
q.pb(i);
}
q.clear();
for (int i = n - 1; i >= 0; i--) {
while (q.size() > 0 && h[q.back()] < h[i]) {
l[q.back()] = i;
q.pop_back();
}
q.pb(i);
}
}
int minimum_jumps(int a, int b, int c, int d) {
int j = c, k = -1;
for (int i = c; i <= d; i++) {
if (h[i] > h[j]) {
j = i;
}
}
for (int i = a; i <= b; i++) {
if (h[i] < h[j] && (k == -1 || h[i] > h[k])) {
k = i;
}
}
if (k == -1) return -1;
int cnt = 1;
while (r[k] < c) {
int L = l[k], R = r[k];
cnt++;
if (L == -1) {
k = R;
} else if (R == -1) {
k = L;
} else {
if (h[L] > h[R] && h[L] < h[j]) {
k = L;
} else {
k = R;
}
}
}
if (r[k] == n) return -1;
return cnt;
}
#ifdef LOCAL
int main() {
while (1) {
int n = rnd() % 5 + 1, q = rnd() % 10 + 1;
vector<int> h(n);
iota(h.begin(), h.end(), 1);
shuffle(h.begin(), h.end(), rnd);
init(n, h);
cout << n << endl;
for (auto to : h) {
cout << to << ' ';
}
cout << endl;
for (int i = 0; i < q; i++) {
vector<int> arr(4);
for (int j = 0; j < 4; j++) arr[j] = rnd() % n;
if (arr[1] >= arr[2]) continue;
cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << ' ' << arr[3] << endl;
minimum_jumps(arr[0], arr[1], arr[2], arr[3]);
}
cout << "ok" << n << endl;
}
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
3104 ms |
3984 KB |
Output is correct |
4 |
Execution timed out |
4067 ms |
5040 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 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 |
208 KB |
Output is correct |
5 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 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 |
208 KB |
Output is correct |
5 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 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 |
208 KB |
Output is correct |
5 |
Correct |
23 ms |
3352 KB |
Output is correct |
6 |
Correct |
28 ms |
4148 KB |
Output is correct |
7 |
Correct |
13 ms |
2204 KB |
Output is correct |
8 |
Incorrect |
29 ms |
4168 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Incorrect |
199 ms |
2092 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Incorrect |
199 ms |
2092 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
3104 ms |
3984 KB |
Output is correct |
4 |
Execution timed out |
4067 ms |
5040 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |