Submission #549792

#TimeUsernameProblemLanguageResultExecution timeMemory
549792fcmalkcinRainforest Jumps (APIO21_jumps)C++17
4 / 100
1118 ms66120 KiB
#include<bits/stdc++.h> using namespace std; #define ll int #define pll pair<ll,ll> #define ff first #define ss second #define endl "\n" #define pb push_back #define F(i,a,b) for(ll i=a;i<=b;i++) const ll maxn=3e5+10 ; const ll base=1e9; const ll mod= 1e9+7 ; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); /// have medal in APIO /// goal 2/8 ll nxtr[maxn][20]; ll nxtl[maxn][20]; ll nxtmx[maxn][20]; ll mxnxtmx[maxn][20]; ll b[maxn]; ll pos[maxn]; void init(ll n,vector<ll> a) { stack<ll> st; for (int t=0;t<20;t++) nxtr[n+1][t]=n+1; for (int i=n;i>=1;i--) { pos[a[i-1]]=i; while (st.size()&&a[st.top()-1]<a[i-1]) st.pop(); if (st.size()) nxtr[i][0]=st.top(); else nxtr[i][0]=n+1; for (int t=1;t<20;t++) nxtr[i][t]=nxtr[nxtr[i][t-1]][t-1]; st.push(i); } while (st.size()) st.pop(); for (int i=1;i<=n;i++) { while (st.size()&&a[st.top()-1]<a[i-1]) st.pop(); if (st.size()) nxtl[i][0]=st.top(); else nxtl[i][0]=0; for (int t=1;t<20;t++) nxtl[i][t]=nxtl[nxtl[i][t-1]][t-1]; st.push(i); } for (int i=n;i>=1;i--) { pll nw=make_pair(0,pos[i]); ll id=pos[i]; if (nxtl[id][0]!=0) { nw=max(nw,make_pair(a[nxtl[id][0]-1],nxtl[id][0])); } if (nxtr[id][0]!=n+1) { nw=max(nw,make_pair(a[nxtr[id][0]-1],nxtr[id][0])); } nxtmx[id][0]=nw.ss; mxnxtmx[id][0]=max((ll)i,nw.ss); for (int t=1;t<20;t++) nxtmx[id][t]=nxtmx[nxtmx[id][t-1]][t-1],mxnxtmx[id][t]=max(mxnxtmx[id][t-1],mxnxtmx[nxtmx[id][t-1]][t-1]); } } ll minimum_jumps(ll a,ll b,ll c,ll d) { a++; b++; c++; d++; ll nw=b; for (int t=19;t>=0;t--) { if (nxtr[nxtl[nw][t]][0]<=d&&nxtl[nw][t]>=a) { nw=nxtl[nw][t]; } } if (nxtr[nw][0]>d) return -1; ll ans=0; for (int t=19;t>=0;t--) { ll h=nxtmx[nw][t]; if (nxtr[h][0]<=d&&mxnxtmx[nw][t]<c) { ans+=(1ll<<t); nw=h; } } // cout <<nw<<" "<<nxtr[nw][0]<<" "<<ans<<endl; for (int t=19;t>=0;t--) { if (nxtr[nw][t]<c) { // cout <<nw<<" "<<t<<" wtf"<<" "<<nxtr[nw][t]<<endl; nw=nxtr[nw][t]; ans+=(1ll<<t); } } ans++; nw=nxtr[nw][0]; // cout <<nw<<" "<<nxtr[nw][0]<<" "<<nxtmx[nw][0]<<" "<<nxtr[nw][0]<<endl; if (nw<=d) { return ans; } else { return -1; } } /*int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll n; cin>> n; vector<ll> vt; for (int i=1;i<=n;i++) { ll x; cin>> x; vt.pb(x); } init(n,vt); ll a,b, c, d; cin>> a>> b>> c>> d; a--; b--; c--; d--; cout <<minimum_jumps(a,b,c,d)<<endl; }*/
#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...