제출 #1228707

#제출 시각아이디문제언어결과실행 시간메모리
1228707abdelhakimRainforest Jumps (APIO21_jumps)C++20
100 / 100
602 ms96016 KiB
#include "jumps.h" #include <bits/stdc++.h> #define ll long long #define inf (ll)(1e15) #define dbg(x) cerr <<#x << ' ' << x <<endl; using namespace std; ll n; vector<ll> h; vector<pair<ll,ll>> mn; vector<ll> ind; vector<ll> limn; vector<vector<ll>> nqqz; vector<vector<ll>> nqqz2; ll maxn=2e5; vector<ll> tree(4*maxn+3); ll rnd(ll l, ll r) { return rand()%(r-l+1)+l; } void update(ll node, ll l, ll r, ll pos, ll val) { if(pos < l || pos > r)return; if(l==r) { tree[node]=val; return; } ll mid=(l+r)/2; update(node*2+1,l,mid,pos,val); update(node*2+2,mid+1,r,pos,val); tree[node]=max(tree[node*2+1],tree[node*2+2]); } ll query(ll node, ll l, ll r, ll x, ll y) { if(max(l,x) > min(r,y))return 0; if(x<=l && r<=y)return tree[node]; ll mid=(l+r)/2; return max(query(node*2+1,l,mid,x,y),query(node*2+2,mid+1,r,x,y)); } void init(int N, std::vector<int> H) { h.clear(); mn.clear(); ind.clear(); limn.clear(); nqqz.clear(); nqqz2.clear(); tree.clear(); n=N; for (int i=0;i<n;i++) h.push_back(H[i]); mn.resize(n+1); stack<ll> s; for (int i=0;i<n;i++) { while(s.size() && (s.top() < h[i])) { s.pop(); } if(s.size()) { mn[h[i]].first=s.top(); } s.push(h[i]); } while(s.size())s.pop(); for (int i=n-1;i>=0;i--) { while(s.size() && (s.top() < h[i])) { s.pop(); } if(s.size()) { mn[h[i]].second=s.top(); } s.push(h[i]); } ind.resize(n+1); for (int i=0;i<n;i++) { ind[h[i]]=i; update(0,0,n-1,i,h[i]); } limn.resize(n+1); for (int i=n-1;i>=0;i--) { if(mn[h[i]].second!=0) { limn[h[i]]=1+limn[mn[h[i]].second]; } } nqqz.assign(n+1,vector<ll>(20,inf)); nqqz2.assign(n+1,vector<ll>(20,inf)); for (int i=n;i>=1;i--) { for (int j=0;j<20;j++) { if(j==0) { if(max(mn[i].first,mn[i].second)!=0) { nqqz[i][j]=max(mn[i].first,mn[i].second); } } else { if(max(mn[i].first,mn[i].second)!=0) { ll x=nqqz[i][j-1]; if(x!=inf) { nqqz[i][j]=nqqz[x][j-1]; } } } } } // tnqiza 2: for (int i=n;i>=1;i--) { for (int j=0;j<20;j++) { if(j==0) { if(mn[i].second!=0) { nqqz2[i][j]=mn[i].second; } } else { if(mn[i].second!=0) { ll x=nqqz2[i][j-1]; if(x!=inf) { nqqz2[i][j]=nqqz2[x][j-1]; } } } } } } int minimum_jumps(int A, int B, int C, int D) { ll kbir=query(0,0,n-1,C,D); if(mn[kbir].first!=0 && ind[mn[kbir].first] >= B) return -1; ll awal; if(mn[h[C]].first==0 || ind[mn[h[C]].first] < B) awal=h[C]; else { awal=h[B]; for (int j=19;j>=0;j--) { if(nqqz2[awal][j] != inf && ind[nqqz2[awal][j]]<C) { awal=nqqz2[awal][j]; } } awal=nqqz2[awal][0]; } // dbg(awal); ll indd=A; if(mn[kbir].first!=0) { indd=max(ind[mn[kbir].first]+1,(ll)A); } ll cur=query(0,0,n-1,indd,B); if(cur > awal) return 1; ll ans=0; for (int j=19;j>=0;j--) { if(nqqz[cur][j]!=inf && nqqz[cur][j]<awal) { cur=nqqz[cur][j]; ans+=1LL<<j; } } if(mn[cur].second==awal) return ans+1; if(mn[cur].first < kbir) return ans+2; return ans + limn[cur]-limn[awal]; } // int minimum_jumps2(int A, int B, int C, int D) { // vector<ll> dp(n+1,inf); // for (int i=n;i>=1;i--) // { // if(C<=ind[i] && ind[i]<=D) // { // dp[i]=0; // // dbg(i); // } // else // { // if(mn[i].first!=0) dp[i]=min(dp[i],1+dp[mn[i].first]); // if(mn[i].second!=0) dp[i]=min(dp[i],1+dp[mn[i].second]); // // cout << "here " << i << ' ' << dp[i] << endl; // } // } // ll ans=inf; // for (int i=A;i<=B;i++) // { // ans=min(ans,dp[h[i]]); // } // if(ans==inf)return -1; // else return ans; // } // void stresstest() // { // for (int j=0;j<500;j++) // {ll n=rnd(2,10); // vector<int> v(n); // for (int i=1;i<=n;i++) v[i-1]=i; // mt19937 rng(j); // shuffle(v.begin(),v.end(),rng); // init(n,v); // vector<ll> indices; // for (int i=0;i<4;i++) // { // ll x=rnd(0,n-1); // indices.push_back(x); // } // sort(indices.begin(),indices.end()); // if(indices[1]==indices[2])continue; // cout << n << endl; // for (auto &&e : v) // { // cout << e << ' '; // } // cout << endl; // cout << "indices "; // for (auto &&e : indices) // { // cout << e << ' '; // } // cout << endl; // ll ans1=minimum_jumps2(indices[0],indices[1],indices[2],indices[3]); // ll ans2=minimum_jumps(indices[0],indices[1],indices[2],indices[3]); // cout << "answers " << ans1 << ' ' << ans2 << endl; // if(ans1!=ans2) // { // break; // } // } // } // int main() // { // stresstest(); // }
#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...