제출 #1201835

#제출 시각아이디문제언어결과실행 시간메모리
1201835aykhnRainforest Jumps (APIO21_jumps)C++20
27 / 100
488 ms35732 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int MXN = 2e5 + 5; const int LOG = 20; int p[2][LOG][MXN]; vector<int> h; void init(int N, vector<int> H) { h = H; int prv[N], nxt[N]; { vector<int> st; for (int i = 0; i < N; i++) { while (!st.empty() && H[i] > H[st.back()]) st.pop_back(); if (st.empty()) prv[i] = -1; else prv[i] = st.back(); st.push_back(i); } } { vector<int> st; for (int i = N - 1; i >= 0; i--) { while (!st.empty() && H[i] > H[st.back()]) st.pop_back(); if (st.empty()) nxt[i] = -1; else nxt[i] = st.back(); st.push_back(i); } } for (int i = 0; i < N; i++) { p[0][0][i] = p[1][0][i] = -1; if (nxt[i] != -1 && prv[i] != -1) { p[0][0][i] = nxt[i], p[1][0][i] = prv[i]; if (H[nxt[i]] > H[prv[i]]) swap(p[0][0][i], p[1][0][i]); } else p[0][0][i] = max(nxt[i], prv[i]); } for (int _ = 0; _ < 2; _++) { for (int i = 1; i < LOG; i++) { for (int j = 0; j < N; j++) { if (p[_][i - 1][j] == -1) { p[_][i][j] = -1; continue; } p[_][i][j] = p[_][i - 1][p[_][i - 1][j]]; } } } } int minimum_jumps(int A, int B, int C, int D) { A = max(A, B), C = min(C, D); int res = 0; for (int _ = 1; _ >= 0 && A != C; _--) { for (int i = LOG - 1; i >= 0; i--) { if (p[_][i][A] == -1) continue; if (h[p[_][i][A]] >= h[C]) continue; A = p[_][i][A]; res += (1 << i); } if (p[_][0][A] != -1 && h[p[_][0][A]] <= h[C]) { A = p[_][0][A]; res++; } } if (A != C) return -1; return res; }
#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...