제출 #814668

#제출 시각아이디문제언어결과실행 시간메모리
814668sentheta밀림 점프 (APIO21_jumps)C++17
4 / 100
1278 ms114660 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], lo[N][LN]; void init(int _n, V<int> _a){ n = _n; rep(i,0,n) a[i] = _a[i]; // leftward edges V<int> stak; rep(i,0,n){ while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back(); int j = stak.empty() ? i : stak.back(); pl[i][0] = j; if(i!=j) adj[i].push_back(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; if(i!=j) adj[i].push_back(j); stak.push_back(i); } rep(i,0,n){ if(adj[i].empty()) adj[i].push_back(i); if(adj[i].size()==1) adj[i].push_back(adj[i][0]); if(!(a[adj[i][0]] <= a[adj[i][1]])){ swap(adj[i][0], adj[i][1]); } lo[i][0] = adj[i][0]; hi[i][0] = adj[i][1]; } rep(lg,1,LN) rep(i,0,n){ 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]; lo[i][lg] = lo[lo[i][lg-1]][lg-1]; } } int minimum_jumps(int A,int B,int C,int D){ // 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] that can reach [C..D] int s = B; for(int b=LN-1; b>=0; b--){ int x = pl[s][b]; if(A<=x && a[x]<=a[t]) s = x; } // impossible if(!(a[s] < a[t])){ return -1; } // directly connected for(int x : adj[s]){ if(C<=x && x<=D) return 1; } int ans = 0; // find closest ancestor that is directly connected // hi edges for(int b=LN-1; b>=0; b--){ bool ok = 1; int x = hi[s][b]; ok &= a[x]<a[t]; ok &= !(C<=x && x<=D); for(int y : adj[x]){ ok &= !(C<=y && y<=D); } if(ok){ s = hi[s][b]; ans += 1<<b; } } // rightward edges // leftward is not possible, since it was skippable for(int b=LN-1; b>=0; b--){ bool ok = 1; int x = pr[s][b]; ok &= a[x]<a[t]; ok &= !(C<=x && x<=D); for(int y : adj[x]){ ok &= !(C<=y && y<=D); } if(ok){ s = pr[s][b]; ans += 1<<b; } } s = pr[s][0]; ans += 2; assert(C<=pr[s][0] && pr[s][0]<=D); 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...