Submission #1201825

#TimeUsernameProblemLanguageResultExecution timeMemory
1201825aykhn밀림 점프 (APIO21_jumps)C++20
33 / 100
4046 ms16072 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int MXN = 2e5 + 5; const int LOG = 20; int n; vector<int> h; vector<int> adj[MXN]; void init(int N, vector<int> H) { n = N, 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++) { for (int j : {nxt[i], prv[i]}) { if (j != -1) adj[i].push_back(j); } } } int minimum_jumps(int A, int B, int C, int D) { // A = max(A, B), C = min(C, D); vector<int> d(n, -1); queue<int> q; for (int i = A; i <= B; i++) d[i] = 0, q.push(i); while (!q.empty()) { int a = q.front(); q.pop(); if (C <= a && a <= D) return d[a]; for (int &v : adj[a]) { if (d[v] == -1) { d[v] = d[a] + 1; q.push(v); } } } return -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...