제출 #769371

#제출 시각아이디문제언어결과실행 시간메모리
769371dxz05밀림 점프 (APIO21_jumps)C++17
44 / 100
1026 ms74056 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int MaxN = 200000; const int Log = 18; int N; int low[MaxN][Log], high[MaxN][Log]; int lf[MaxN][Log], rg[MaxN][Log]; int rmq[MaxN][Log]; vector<int> H; void init(int _N, vector<int> _H) { N = _N, H = _H; stack<int> st; for (int i = 0; i < N; i++){ while (!st.empty() && H[st.top()] < H[i]) st.pop(); lf[i][0] = (st.empty() ? -1 : st.top()); st.push(i); } while (!st.empty()) st.pop(); for (int i = N - 1; i >= 0; i--){ while (!st.empty() && H[st.top()] < H[i]) st.pop(); rg[i][0] = (st.empty() ? -1 : st.top()); st.push(i); } memset(low, -1, sizeof(low)); memset(high, -1, sizeof(high)); for (int i = 0; i < N; i++){ int l = lf[i][0], r = rg[i][0]; if (l == -1 && r == -1) continue; if (l != -1 && r != -1){ low[i][0] = (H[l] < H[r] ? l : r); high[i][0] = (H[l] > H[r] ? l : r); } else { low[i][0] = high[i][0] = (l != -1 ? l : r); } } for (int j = 1; j < Log; j++){ for (int i = 0; i < N; i++){ if (low[i][j - 1] != -1){ low[i][j] = low[low[i][j - 1]][j - 1]; } if (high[i][j - 1] != -1){ high[i][j] = high[high[i][j - 1]][j - 1]; } if (lf[i][j - 1] != -1){ lf[i][j] = lf[lf[i][j - 1]][j - 1]; } else { lf[i][j] = -1; } if (rg[i][j - 1] != -1){ rg[i][j] = rg[rg[i][j - 1]][j - 1]; } else { rg[i][j] = -1; } } } for (int i = 0; i < N; i++) rmq[i][0] = H[i]; for (int j = 1; j < Log; j++){ for (int i = 0; i + (1 << j) - 1 < N; i++){ rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]); } } } int minimum_jumps(int A, int B, int C, int D) { int z = 31 - __builtin_clz(D - C + 1); int mx = max(rmq[C][z], rmq[D - (1 << z) + 1][z]); int ans = 0; int v = B; for (int i = Log - 1; i >= 0; i--){ int u = lf[v][i]; if (u != -1 && u >= A && H[u] <= mx) v = u; } for (int i = Log - 1; i >= 0; i--){ int u = high[v][i]; if (u != -1 && H[u] <= mx){ ans += 1 << i; v = u; } } for (int i = Log - 1; i >= 0; i--){ int u = rg[v][i]; if (u != -1 && u < C){ ans += 1 << i; v = u; } } if (v < C){ v = rg[v][0]; ans++; } return (C <= v && v <= D ? 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...