제출 #814783

#제출 시각아이디문제언어결과실행 시간메모리
814783sentheta밀림 점프 (APIO21_jumps)C++17
100 / 100
1187 ms50532 KiB
#include "jumps.h" #include<bits/stdc++.h> #ifdef VANWIJ #define DBG 1 #else #define DBG 0 #endif using namespace std; #define Int long long #define V vector #define pii pair<int,int> #define ff first #define ss second static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pow2(x) (1LL<<(x)) #define msb(x) (63-__builtin_clzll(x)) #define bitcnt(x) (__builtin_popcountll(x)) #define nl '\n' #define _ << ' ' << #define all(x) (x).begin(), (x).end() #define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++) #define cerr if(DBG) cout #define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;} const int N = 2e5+5; const int LN = 18; int n; int a[N]; V<int> adj[N]; int pl[N][LN], pr[N][LN]; int hi[N][LN]; void init(int _n, V<int> _a){ n = _n; a[0] = a[n+1] = n+1; rep(i,1,n+1) a[i] = _a[i-1]; // leftward edges V<int> stak; for(int i=0; i<=n+1; i++){ while(!stak.empty() && a[stak.back()]<=a[i]) stak.pop_back(); int j = stak.empty() ? i : stak.back(); pl[i][0] = j; stak.push_back(i); } // rightward edges stak.clear(); for(int i=n+1; i>=0; i--){ while(!stak.empty() && a[stak.back()]<=a[i]) stak.pop_back(); int j = stak.empty() ? i : stak.back(); pr[i][0] = j; dbg(i); dbg(j); cerr << nl; stak.push_back(i); } for(int i=0; i<=n+1; i++){ if(a[pl[i][0]] > a[pr[i][0]]){ hi[i][0] = pl[i][0]; } else{ hi[i][0] = pr[i][0]; } } dbg(pr[4][0]); dbg(pr[n+1][0]); rep(lg,1,LN) for(int i=0; i<=n+1; i++){ pl[i][lg] = pl[pl[i][lg-1]][lg-1]; pr[i][lg] = pr[pr[i][lg-1]][lg-1]; hi[i][lg] = hi[hi[i][lg-1]][lg-1]; } } int minimum_jumps(int A,int B,int C,int D){ A++; B++; C++; D++; // touching if(B==C-1){ if(pr[B][0] <= D) return 1; return -1; } // maximum in [B+1..C-1] int m = B+1; for(int b=LN-1; b>=0; b--){ int x = pr[m][b]; if(x<C) m = x; } if(a[B] > a[m]){ if(pr[B][0] <= D) return 1; return -1; } // // maximum in [C..D] // int t = C; // for(int b=LN-1; b>=0; b--){ // int x = pr[t][b]; // if(x<=D) t = x; // } // maximum in [A..B] not over a[m] int s = B; for(int b=LN-1; b>=0; b--){ int x = pl[s][b]; if(A<=x && a[x]<a[m]) s = x; } // // impossible // if(!(a[s] < a[t])) return -1; // if(!(a[m] < a[t])) return -1; // // if jump over m // for(int x : adj[s]){ // if(C<=x && x<=D) return 1; // } // WLOG a[s] < a[m] // jump over m int ans = 0; // there is better in interval if(A <= pl[s][0]){ // if jump over int x = pr[pl[s][0]][0]; if(C<=x && x<=D) return 1; // no need to go left since it will land at over a[t] } else{ // hi edges, not passing a[m] for(int b=LN-1; b>=0; b--){ int x = hi[s][b]; if(a[x]<=a[m]){ s = x; ans += 1<<b; } } // stopped at m if(s==m){ if(C<=pr[s][0] && pr[s][0]<=D) return ans+1; return -1; } // if jump over { int x = pr[pl[s][0]][0]; if(C<=x && x<=D) return ans+2; } } // rightward edges // leftward is not possible, since it coulve been skipped for(int b=LN-1; b>=0; b--){ int x = pr[s][b]; if(x < C){ s = x; ans += 1<<b; } } s = pr[s][0]; ans++; if(C<=s && s<=D) return ans; 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...