제출 #815283

#제출 시각아이디문제언어결과실행 시간메모리
815283sentheta밀림 점프 (APIO21_jumps)C++17
4 / 100
903 ms50436 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int mxN = 2e5 + 5; const int lg = 20; int a[mxN], righ[mxN][lg], lef[mxN][lg], best[mxN][lg]; void init(int N, vector<int> H) { for (int i = 1; i <= N; i++) a[i] = H[i - 1]; stack<int> st; for (int i = 1; i <= N; i++) { while (!st.empty() && a[st.top()] < a[i]) st.pop(); if (st.empty()) lef[i][0] = i; else lef[i][0] = st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i = N; i >= 1; i--) { while (!st.empty() && a[st.top()] < a[i]) st.pop(); if (st.empty()) righ[i][0] = i; else righ[i][0] = st.top(); st.push(i); } for (int i = 1; i <= N; i++) { if (a[righ[i][0]] > a[lef[i][0]]) best[i][0] = righ[i][0]; else best[i][0] = lef[i][0]; } for (int j = 1; j < lg; j++) { for (int i = 1; i <= N; i++) { best[i][j] = best[best[i][j - 1]][j - 1]; righ[i][j] = righ[righ[i][j - 1]][j - 1]; lef[i][j] = lef[lef[i][j - 1]][j - 1]; } } } int get_max(int l, int r, int v) { if (a[r] > v) return -1; for (int j = lg - 1; j >= 0; j--) { if (lef[r][j] >= l && a[lef[r][j]] < v) r = lef[r][j]; } return r; } int minimum_jumps(int A, int B, int C, int D) { A++, B++, C++, D++; // top in each intervals [A..B], [B+1..C-1], [C..D] int midx = get_max(C, D, 1e9); int start = get_max(A, B, a[midx]); if (start == -1) return -1; if (B == C - 1) return 1; int barrier = a[get_max(B + 1, C - 1, 1e9)]; if (barrier < a[start]) return 1; if (barrier > a[midx]) return -1; // climb until barrier using skip-edge aka. high-edge int ans = 0; for (int j = lg - 1; j >= 0; j--) { if (a[best[start][j]] <= barrier) start = best[start][j], ans += (1 << j); } // end up at barrier if (a[start] == barrier) return ans + 1; // jump over barrier if (a[best[start][0]] < a[midx]) return ans + 2; // if not jump over, the must move to right approaching target for (int j = lg - 1; j >= 0; j--) { if (a[righ[start][j]] < C) start = righ[start][j], ans += (1 << j); } return ans + 1; }
#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...