Submission #1228707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228707		abdelhakim	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	602 ms	96016 KiB

jumps

#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();
// }

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19