이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#ifndef LOCAL
#include "jumps.h"
#endif
#define ld long double
#define ll long long
#define pb push_back
const int INF = 1e9;
using namespace std;
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, -1);
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 = -1, k = -1;
for (int i = c; i <= d; i++) {
if (j == -1 || 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;
}
}
}
return cnt;
}
#ifdef LOCAL
int main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int A, B, C, D;
assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}
#endif
# | 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... |