제출 #557220

#제출 시각아이디문제언어결과실행 시간메모리
557220new_acc밀림 점프 (APIO21_jumps)C++14
48 / 100
995 ms48984 KiB
#include<bits/stdc++.h> #include "jumps.h" #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vl; const int N=2e5+10; const int SS=1<<19; const int INFi=2e9; const ll INFl=1e13; const ll mod2=998244353; const ll mod=1e9+7; const ll mod3=1000696969; const ll p=70032301; const ull p2=913; const int L=18; int t[N],l[N][L+1],r[N][L+1],w[N][L+1],n; void init(int nn,vi v){ n=nn; for(int i=1;i<=n;i++) t[i]=v[i-1]; deque<pair<int,int> >deq; for(int i=n;i>=1;i--){ while(deq.size() and deq.back().fi<t[i]) deq.pop_back(); if(!deq.size()) r[i][0]=n+1; else r[i][0]=deq.back().se; deq.push_back({t[i],i}); } deq.clear(); for(int i=1;i<=n;i++){ while(deq.size() and deq.back().fi<t[i]) deq.pop_back(); if(!deq.size()) l[i][0]=0; else l[i][0]=deq.back().se; deq.push_back({t[i],i}); } for(int i=0;i<=L;i++) r[n+1][i]=n+1; for(int i=1;i<=n;i++){ for(int k=1;k<=L;k++) l[i][k]=l[l[i][k-1]][k-1]; } for(int i=n;i>=1;i--){ for(int k=1;k<=L;k++) r[i][k]=r[r[i][k-1]][k-1]; } t[n+1]=INFi; for(int i=1;i<=n;i++){ if((r[i][0]==n+1 and l[i][0]!=0) or t[l[i][0]]>t[r[i][0]]) w[i][0]=l[i][0]; else w[i][0]=r[i][0]; } for(int i=0;i<=L;i++) w[n+1][i]=n+1; for(int i=1;i<=L;i++){ for(int k=1;k<=n;k++) w[k][i]=w[w[k][i-1]][i-1]; } } int minimum_jumps(int a,int b,int c,int d){ a++,b++,c++,d++; int cc=c; for(int i=L;i>=0;i--) if(r[cc][i]<=d) cc=r[cc][i]; if(t[b]>t[cc]) return -1; int bb=b; for(int i=L;i>=0;i--) if(l[bb][i]>=a and t[l[bb][i]]<t[cc]) bb=l[bb][i]; int curr=0; for(int i=L;i>=0;i--) if(t[w[bb][i]]<t[cc] and w[bb][i]<c) bb=w[bb][i],curr+=(1<<i); int res=-1; for(int i=L;i>=0;i--){ if(r[bb][i]<c) curr+=(1<<i),bb=r[bb][i]; else res=curr+(1<<i); } if(r[bb][0]>d) return -1; return res; } /*int main(){ int n; cin>>n; vi xd; for(int i=1;i<=n;i++){ int a; cin>>a; xd.push_back(a); } init(n,xd); int q; cin>>q; while(q--){ int a,b,c,d; cin>>a>>b>>c>>d; cout<<minimum_jumps(a,b,c,d)<<"\n"; } }*/
#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...