제출 #740484

#제출 시각아이디문제언어결과실행 시간메모리
740484Berryisbetter밀림 점프 (APIO21_jumps)C++17
0 / 100
228 ms6432 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; using ll=long long; vector<ll> seg,br,d;ll n; ll qw(ll a,ll b){ ll ans=0; for (a+=n,b+=n;a<b;a/=2,b/=2){ if (a%2){ ans=max(ans,seg[a]); a++; } if (b%2){ b--; ans=max(ans,seg[b]); } } return ans; } ll ind(ll v,ll a,ll b){ if (a==b){ return a; } ll m=(a+b)/2; if (qw(a,m)>=v){ return ind(v,a,m); } return ind(v,m+1,b); } /*#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ll n; cin >> n; vector<ll> a(n), r(n); for (ll i = 0; i < n; i++) { cin >> a[i]; r[i] = i - 1; } for (ll i = 0; i < n; i++) { ll j = i; while (r[j] != -1) { if (a[i] > a[r[j]]) { break; } j = r[j]; } r[i] = r[j]; cout << r[i] + 1 << '\n'; } }*/ void init(int N, std::vector<int> H) { n=N; seg=vector<ll>(2*n,0); //segment setup for (ll i=0;i<n;i++){ seg[i+n]=H[i]; } for (ll i=n;i>0;i--){ seg[i]=max(seg[2*i],seg[2*i+1]); } //br setup br=vector<ll>(n,0);for (ll i=0;i<n;i++){br[i]=i+1;} for (ll i = n-1; i >= 0; i--) { ll j = i; while (br[j] != n) { if (H[i] < H[br[j]]) { break; } j = br[j]; } br[i] = br[j]; } //distance d=vector<ll>(n+1);d[n]=0; for (ll i=0;i<n;i++){ d[i]=d[br[i]]+1; } } //ind,qw,d int minimum_jumps(int A, int B, int C, int D) { ll x=ind(seg[B+n],seg[C+n],seg[D+n]); if (d[B]>d[x]){ return d[B]-d[x]; } 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...