#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
vector<int> r;
vector<int> l;
void init(int N, std::vector<int> H) {
n = N;
for (auto u: H) {h.push_back(u);}
h.shrink_to_fit();
r.resize(n);
l.resize(n);
for (int i=0; i<n; i++)
{
r[i] = -1;
for (int j=i; j<n; j++)
{
if (h[j] > h[i]) {r[i] = j; break;};
}
}
for (int i=0; i<n; i++)
{
l[i] = -1;
for (int j=i; j>=0; j--)
{
if (h[j] > h[i]) {l[i] = j; break;}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
vector<int> start;
vector<int> end;
vector<bool> stop(n);
for (int i=A; i<=B; i++) {start.push_back(h[i]);}
for (int i=C; i<=D; i++) {end.push_back(h[i]); stop[i] = true;}
sort(start.begin(), start.end());
sort(end.begin(), end.end());
if (end.back() < start[0]) {return -1;}
int point = A;
for (int i=0; i<(int)start.size(); i++) {if (start[i] < end.back()) point = A+i;}
int answer = 0;
for (int i=0; i<n; i++)
{
answer++;
int pre = l[point]; int suff = r[point];
if (stop[pre] || stop[suff]) {break;}
if (pre != -1 && h[pre] < end.back())
{
if (h[pre] > h[point]) {point = pre;}
}
if (suff != -1 && h[suff] < end.back())
{
if (h[suff] > h[point]) {point = suff;}
}
}
return answer;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |