제출 #566688

#제출 시각아이디문제언어결과실행 시간메모리
566688Ooops_sorry밀림 점프 (APIO21_jumps)C++14
0 / 100
4035 ms3356 KiB
#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, n); deque<int> q; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (h[i] > h[j]) { r[j] = min(r[j], i); } } for (int j = i - 1; j >= 0; j--) { if (h[i] > h[j]) { l[j] = max(l[j], 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; } } } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...