제출 #718687

#제출 시각아이디문제언어결과실행 시간메모리
718687lam밀림 점프 (APIO21_jumps)C++14
0 / 100
276 ms44104 KiB
#include "jumps.h" #include <bits/stdc++.h> #include <vector> using namespace std; const int maxn = 2e5 + 10; int n; int a[maxn],b[maxn],d[maxn]; vector <int> adj[maxn]; int par[20][maxn]; int f[20][maxn],g[20][maxn]; void create() { for (int i=0; i<n; i++) f[0][i] = b[i]; for (int j=1; (1<<j)<=n; j++) for (int i=0; i+(1<<j)-1<n; i++) f[j][i] = max(f[j-1][i],f[j-1][i+(1<<(j-1))]); } int get(int l, int r) { if (l>r) return -1; int k=log2(r-l+1); return max(f[k][l],f[k][r-(1<<k)+1]); } void addedge(int u, int v) { adj[u].push_back(v); } void init(int N, std::vector<int> H) { n=N; for (int i=0; i<n; i++) a[i]=H[i],adj[i].clear(); deque<int> dq; for (int i=n-1; i>=0; i--) { while (!dq.empty()&&a[dq.back()] < a[i]) dq.pop_back(); if (!dq.empty()) b[i] = dq.back(), d[i]=d[dq.back()]+1; else b[i] = -1,d[i]=0; dq.push_back(i); } while (!dq.empty()) dq.pop_back(); for (int i=0; i<n; i++) { while (!dq.empty()&&a[dq.back()] < a[i]) dq.pop_back(); if (!dq.empty()) par[0][i] = dq.back(), g[0][i] = d[i]; else par[0][i]=-1, g[0][i] = -1e9; dq.push_back(i); } create(); for (int i=0; i<n; i++) for (int j=1; j<20; j++) if (par[j-1][i]==-1) par[j][i]=-1,g[j][i] = -1e9; else { par[j][i]=par[j-1][par[j-1][i]]; g[j][i] = max(g[j-1][i],g[j-1][par[j-1][i]]); } } int minimum_jumps(int A, int B, int C, int D) { if (A==C) return 0; if (a[A] > a[C]) return -1; int smx = get(B+1,C-1); if (smx > a[C]) return -1; int ans = 1e9; if (smx < a[C]) ans = d[A] - d[C]; int u=A; for (int i=19; i>=0; i--) if (par[i][u]!=-1&&a[par[i][u]] < a[C]) { ans = min(ans,g[i][u]-d[C]); u=par[i][u]; } return ans; }
#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...