제출 #979703

#제출 시각아이디문제언어결과실행 시간메모리
979703nnin밀림 점프 (APIO21_jumps)C++14
48 / 100
819 ms42920 KiB
#include "jumps.h" #include <bits/stdc++.h> #define pii pair<int,int> using namespace std; int n, l[200005], r[200005], jump[200005][20], jump2[200005][20]; vector<int> h; struct segTree { pii seg[4*200005]; void build(int i, int l, int r) { if(l==r) { seg[i] = {h[l], l}; return; } int m = (l+r)/2; build(i*2+1, l, m); build(i*2+2, m+1, r); seg[i] = max(seg[i*2+1], seg[i*2+2]); } pii query(int i, int l, int r, int wl, int wr) { if(wl>r || wr<l) return {-2e9, -1}; if(wl<=l && wr>=r) return seg[i]; int m = (l+r)/2; return max(query(i*2+1, l, m, wl, wr), query(i*2+2, m+1, r, wl, wr)); } }t; void init(int N, std::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(); if(st.empty()) l[i] = -1; else l[i] = 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(); if(st.empty()) r[i] = n; else r[i] = st.top(); st.push(i); } t.build(0, 0, n-1); h.push_back(n+1); for(int i=0;i<n;i++) { int mx = l[i], mx2 = r[i]; if(mx==-1) mx = n; if(h[mx]<h[mx2]) swap(mx, mx2); jump[i][0] = mx; jump2[i][0] = mx2; } jump[n][0] = jump2[n][0] = n; for(int j=1;j<20;j++) for(int i=0;i<=n;i++) jump[i][j] = jump[jump[i][j-1]][j-1]; for(int j=1;j<20;j++) for(int i=0;i<=n;i++) jump2[i][j] = jump2[jump2[i][j-1]][j-1]; } int minimum_jumps(int A, int B, int C, int D) { A = t.query(0, 0, n-1, max(A, l[C]+1), min(B, r[C]-1)).second; if(A==-1) return -1; int ans = 0; for(int i=19;i>=0;i--) if(h[jump[A][i]]<h[C]) { A = jump[A][i]; ans += (1<<i); } if(jump[A][0]==C) return ans+1; for(int i=19;i>=0;i--) if(h[jump2[A][i]]<h[C]) { A = jump2[A][i]; ans += (1<<i); } if(jump2[A][0]==C) return ans+1; 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...