이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
typedef vector < int > vint;
const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;
int n;
int h[mxn] , le[mxn] , ri[mxn];
int spx[19][mxn] , spn[19][mxn];
void init(int N , vint H) {
n = N;
vector < int > v;
for (int i = 0; i < n; i++) {
h[i] = H[i];
}
for (int i = 0; i < n; i++) {
while (v.back()< h[i] && !v.empty()) {
ri[v.back()] = h[i];
v.pop_back();
}
if (!v.empty()) le[i] = v.back();
v.push_back(h[i]);
}
for (int i = 0; i < n; i++) {
spx[0][h[i]] = max(le[h[i]] , ri[h[i]]);
spn[0][h[i]] = min(le[h[i]] , ri[h[i]]);
if (spn[0][h[i]] == 0) spn[0][h[i]] = spx[0][h[i]];
}
for (int j = 1; j < 19; j++) {
for (int i = 0; i < n; i++) {
spx[j][h[i]] = spx[j-1][spx[j-1][h[i]]];
spn[j][h[i]] = spn[j-1][spn[j-1][h[i]]];
}
}
}
int minimum_jumps(int a , int b , int c , int d) {
if (h[a] > h[d]) return -1;
int dis = 0;
for (int i = 18; i >= 0; i--) {
if (spx[i][h[a]] > h[d]) continue;
if (spx[i][h[a]] == h[d]) return (1 << i);
return (1 << i) + minimum_jumps(spx[i][h[a]] , b , c , d);
}
for (int i = 18; i >= 0; i--) {
if (spn[i][h[a]] > h[d]) continue;
if (spn[i][h[a]] == h[d]) return (1 << i);
return (1 << i) + minimum_jumps(spn[i][h[a]] , b , c , d);
}
return -1;
}
컴파일 시 표준 에러 (stderr) 메시지
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:53:6: warning: unused variable 'dis' [-Wunused-variable]
53 | int dis = 0;
| ^~~
# | 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... |