Submission #569517

#TimeUsernameProblemLanguageResultExecution timeMemory
569517S2speedRainforest Jumps (APIO21_jumps)C++17
27 / 100
1160 ms72256 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") #define all(x) x.begin() , x.end() #define sze(x) (ll)(x.size()) #define mp(x , y) make_pair(x , y) #define wall cerr<<"--------------------------------------"<<endl typedef long long int ll; typedef pair<ll , ll> pll; typedef pair<int , int> pii; typedef long double db; typedef pair<pll , ll> plll; typedef pair<int , pii> piii; typedef pair<pll , pll> pllll; const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e16; ll gcd(ll a , ll b){ if(a < b) swap(a , b); if(b == 0) return a; return gcd(b , a % b); } inline ll tav(ll n , ll k){ ll res = 1; while(k > 0){ if(k & 1){ res *= n; res %= md; } n *= n; n %= md; k >>= 1; } return res; } struct segtree { int sz = 1; vector<int> val; void init(int n){ while(sz < n) sz <<= 1; val.assign(sz << 1 , 0); return; } void build(vector<int> &a , int x , int lx , int rx){ if(rx - lx == 1){ if(lx < sze(a)){ val[x] = a[lx]; } return; } int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; build(a , ln , lx , m); build(a , rn , m , rx); val[x] = max(val[ln] , val[rn]); return; } void build(vector<int> &a){ build(a , 0 , 0 , sz); return; } void set(int i , int k , int x , int lx , int rx){ if(rx - lx == 1){ val[x] = k; return; } int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; if(i < m){ set(i , k , ln , lx , m); } else { set(i , k , rn , m , rx); } val[x] = max(val[ln] , val[rn]); return; } void set(int i , int k){ set(i , k , 0 , 0 , sz); return; } int cal(int l , int r , int x , int lx , int rx){ if(rx <= l || lx >= r) return 0; if(rx <= r && lx >= l) return val[x]; int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; int a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx); return max(a , b); } int cal(int l , int r){ return cal(l , r , 0 , 0 , sz); } void clear(){ sz = 1; val.clear(); return; } }; int n; segtree st; vector<int> a , v; int lf[maxn] , rt[maxn] , jal[maxn][20] , jar[maxn][20] , jan[maxn][20] , jax[maxn][20]; vector<pii> u; int p[maxn]; void init(int N, vector<int> H){ memset(jal , -1 , sizeof(jal)); memset(jar , -1 , sizeof(jar)); memset(jan , -1 , sizeof(jan)); memset(jax , -1 , sizeof(jax)); a = H; n = N; for(int i = 0 ; i < n ; i++){ p[a[i]] = i; } for(int i = 0 ; i < n ; i++){ int h = -1; while(!v.empty()){ int j = v.back(); if(a[j] > a[i]){ h = j; break; } v.pop_back(); } lf[i] = h; v.push_back(i); } v.clear(); for(int i = n - 1 ; ~i ; i--){ int h = -1; while(!v.empty()){ int j = v.back(); if(a[j] > a[i]){ h = j; break; } v.pop_back(); } rt[i] = h; v.push_back(i); } for(int i = 0 ; i < n ; i++){ jal[i][0] = lf[i]; for(int j = 1 ; j < 20 ; j++){ if(jal[i][j - 1] == -1) break; jal[i][j] = jal[jal[i][j - 1]][j - 1]; } } for(int i = n - 1 ; ~i ; i--){ jar[i][0] = rt[i]; for(int j = 1 ; j < 20 ; j++){ if(jar[i][j - 1] == -1) break; jar[i][j] = jar[jar[i][j - 1]][j - 1]; } } for(int i = 0 ; i < n ; i++){ u.push_back({a[i] , i}); } sort(all(u) , greater<pii>()); for(int e = 1 ; e < n ; e++){ int i = u[e].second; if(lf[i] == -1){ jax[i][0] = rt[i]; } else if(rt[i] == -1){ jax[i][0] = lf[i]; } else { if(a[lf[i]] > a[rt[i]]){ jax[i][0] = lf[i]; jan[i][0] = rt[i]; } else { jax[i][0] = rt[i]; jan[i][0] = lf[i]; } } for(int j = 1 ; j < 20 ; j++){ if(jax[i][j - 1] == -1) break; jax[i][j] = jax[jax[i][j - 1]][j - 1]; } for(int j = 1 ; j < 20 ; j++){ if(jan[i][j - 1] == -1) break; jan[i][j] = jan[jan[i][j - 1]][j - 1]; } } st.init(n); st.build(a); return; } int dis(int x , int y){ int res = 0; for(int j = 19 ; ~j ; j--){ int h = jax[x][j]; if(h == -1) continue; if(a[h] > a[y]) continue; res += (1 << j); x = h; } for(int j = 19 ; ~j ; j--){ int h = jan[x][j]; if(h == -1) continue; if(a[h] > a[y]) continue; res += (1 << j); x = h; } return (x == y ? res : -2); } int minimum_jumps(int l1, int r1, int l2, int r2){ r1++; r2++; if(r1 == l1){ if(rt[r1 - 1] == -1 || rt[r1 - 1] >= r2) return -1; return 1; } int d = st.cal(r1 , l2) , k = st.cal(l2 , r2); if(d > k) return -1; if(a[r1 - 1] > d){ if(a[r1 - 1] > k) return -1; return 1; } int v = r1 - 1; for(int j = 19 ; ~j ; j--){ int h = jal[v][j]; if(h < l1) continue; if(a[h] > d) continue; v = h; } int res = dis(v , p[d]) + 1; if(lf[v] >= l1) return 1; int o = v; for(int j = 19 ; ~j ; j--){ int h = jal[o][j]; if(h == -1) continue; if(a[h] > d) continue; o = h; } o = lf[o]; if(o == -1) return res; if(a[o] > k) return res; int h = dis(v , o); if(h != -2){ res = min(res , h + 1); if(res == -1) res = h + 1; } return res; }
#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...