제출 #769318

#제출 시각아이디문제언어결과실행 시간메모리
769318dxz05밀림 점프 (APIO21_jumps)C++17
44 / 100
1025 ms59880 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]; 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; } } } } int minimum_jumps(int A, int B, int C, int D) { if (C != D) return 0; 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] <= H[C]) v = u; } for (int i = Log - 1; i >= 0; i--){ int u = high[v][i]; if (u != -1 && H[u] <= H[C]){ ans += 1 << i; v = u; } } for (int i = Log - 1; i >= 0; i--){ int u = low[v][i]; if (u != -1 && H[u] <= H[C]){ ans += 1 << i; v = u; } } 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...