제출 #951483

#제출 시각아이디문제언어결과실행 시간메모리
951483hengliao밀림 점프 (APIO21_jumps)C++17
4 / 100
705 ms90368 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define vll vector<ll> #define pll pair<ll, ll> typedef long long ll; const ll mxN=2e5+5; const ll inf=1e18; ll n; vll h; vll adj[mxN]; ll r[mxN]; ll l[mxN]; vll dis; bool cool; ll up[mxN][20]; ll up2[mxN][20]; ll bg[mxN]; ll sm[mxN]; void init(int tn, vector<int> th){ n=tn; h.resize(n); cool=1; for(ll i=0;i<n;i++){ h[i]=th[i]; if(h[i]!=i+1){ cool=0; } } vector<ll> stk; for(ll i=0;i<n;i++){ if(!stk.empty()){ ll lef=0, rig=stk.size()-1; ll tep=inf; while(lef<=rig){ ll mid=(lef+rig)/2; if(stk[mid]>h[i]){ tep=min(tep, stk[mid]); lef=mid+1; } else{ rig=mid-1; } } l[h[i]]=tep; } else{ l[h[i]]=inf; } while(!stk.empty() && stk.back()<h[i]){ stk.pop_back(); } stk.pb(h[i]); } stk.clear(); for(ll i=n-1;i>=0;i--){ if(!stk.empty()){ ll lef=0, rig=stk.size()-1; ll tep=inf; while(lef<=rig){ ll mid=(lef+rig)/2; if(stk[mid]>h[i]){ tep=min(tep, stk[mid]); lef=mid+1; } else{ rig=mid-1; } } r[h[i]]=tep; } else{ r[h[i]]=inf; } while(!stk.empty() && stk.back()<h[i]){ stk.pop_back(); } stk.pb(h[i]); } for(ll i=1;i<=n;i++){ if(l[i]!=inf){ adj[i].pb(l[i]); } if(r[i]!=inf){ adj[i].pb(r[i]); } } for(ll i=1;i<=n;i++){ if(l[i]==inf && r[i]==inf){ bg[i]=inf; sm[i]=inf; } else if(l[i]==inf){ bg[i]=r[i]; sm[i]=inf; } else if(r[i]==inf){ bg[i]=l[i]; sm[i]=inf; } else{ bg[i]=max(l[i], r[i]); sm[i]=min(l[i], r[i]); } up[i][0]=bg[i]; up2[i][0]=sm[i]; } for(ll i=1;i<20;i++){ for(ll j=1;j<=n;j++){ if(up[j][i-1]!=inf) up[j][i]=up[up[j][i-1]][i-1]; else up[j][i]=inf; } } for(ll i=1;i<=20;i++){ for(ll j=1;j<=n;j++){ if(up2[j][i-1]!=inf) up2[j][i]=up2[up2[j][i-1]][i-1]; else up2[j][i]=inf; } } //cout<<"initializing\n"; //for(ll i=1;i<=n;i++){ //cout<<i<<' '<<l[i]<<' '<<r[i]<<'\n'; //} } int minimum_jumps(int a, int b, int c, int d){ if(cool) return c-b; if(a==b && c==d){ a=h[a]; c=h[c]; ll ans=0; for(ll i=19;i>=0;i--){ if(up[a][i]<=c){ ans+=(1LL<<i); a=up[a][i]; } } for(ll i=19;i>=0;i--){ if(up2[a][i]<=c){ ans+=(1LL<<i); a=up2[a][i]; } } if(a!=c){ return -1; } else{ return (int) ans; } } dis=vll(n+1, inf); queue<pll> q; for(ll i=a;i<=b;i++){ q.push({h[i], 0}); } while(!q.empty()){ pll cur=q.front(); q.pop(); if(dis[cur.F]!=inf){ continue; } dis[cur.F]=cur.S; for(auto it:adj[cur.F]){ q.push({it, cur.S+1}); } } ll re=inf; for(ll i=c;i<=d;i++){ re=min(re, dis[h[i]]); //cout<<h[i]<<' '<<dis[h[i]]<<'\n'; } if(re==inf) return -1; else return (int) re; } /*int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin>>n>>q; vector<int> h(n); for(ll i=0;i<n;i++){ cin>>h[i]; } init(n, h); for(ll i=0;i<q;i++){ int a, b, c, d; cin>>a>>b>>c>>d; cout<<minimum_jumps(a, b, c, d)<<'\n'; } return 0; }*/
#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...