Submission #1197692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197692		hengliao	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	612 ms	130356 KiB

jumps

#include "jumps.h"
#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;

namespace{
  const ll mxN=2e5+5;
  const ll LOG=20;
  
  ll n;
  ll h[mxN];
  ll id[mxN];
  ll rmq1[mxN][LOG];
  ll rmq2[mxN][LOG];
  ll up1[mxN][LOG];
  ll up2[mxN][LOG];

  ll rmax(ll a, ll b){
    ll lg=31-__builtin_clz(b-a+1);
    return max(rmq1[a][lg], rmq1[b-(1LL<<lg)+1][lg]);
  }

  ll rmin(ll a, ll b){
    ll lg=31-__builtin_clz(b-a+1);
    return min(rmq2[a][lg], rmq2[b-(1LL<<lg)+1][lg]);
  }

  ll f1(ll a, ll b, ll val){
    ll lef=a, rig=b;
    ll re=-1;
    while(lef<=rig){
      ll mid=(lef+rig)/2;
      if(rmax(a, mid)>=val){
        re=mid;
        rig=mid-1;
      }
      else{
        lef=mid+1;
      }
    }
    return re;
  }

  ll f2(ll a, ll b, ll val){
    ll lef=a, rig=b;
    ll re=-1;
    while(lef<=rig){
      ll mid=(lef+rig)/2;
      if(rmax(mid, b)>=val){
        re=mid;
        lef=mid+1;
      }
      else{
        rig=mid-1;
      }
    }
    return re;
  }
}

void init(int N, std::vector<int> H) {
  n=N;
  for(ll i=0;i<n;i++){
    h[i]=H[i]-1;
    id[h[i]]=i;
  }
  for(ll i=0;i<n;i++){
    rmq1[i][0]=h[i];
    rmq2[i][0]=h[i];
  }
  for(ll j=1;j<LOG;j++){
    for(ll i=0;i+(1LL<<j)-1<n;i++){
      rmq1[i][j]=max(rmq1[i][j-1], rmq1[i+(1LL<<(j-1))][j-1]);
      rmq2[i][j]=min(rmq2[i][j-1], rmq2[i+(1LL<<(j-1))][j-1]);
    }
  }
  for(ll i=0;i<n;i++){
    ll f=f1(i+1, n-1, h[i]);
    ll s=f2(0, i-1, h[i]);
    if(f==-1 && s==-1){
      up1[i][0]=-1;
      up2[i][0]=-1;
    }
    else if(f==-1){
      up1[i][0]=s;
      up2[i][0]=-1;
    }
    else if(s==-1){
      up1[i][0]=f;
      up2[i][0]=-1;
    }
    else{
      if(h[f]>h[s]){
        up1[i][0]=f;
        up2[i][0]=s;
      }
      else{
        up1[i][0]=s;
        up2[i][0]=f;
      }
    }
    // cout<<i<<' '<<up1[i][0]<<' '<<up2[i][0]<<'\n';
  }
  for(ll j=1;j<LOG;j++){
    for(ll i=0;i<n;i++){
      if(up1[i][j-1]!=-1) up1[i][j]=up1[up1[i][j-1]][j-1];
      else up1[i][j]=-1;
      if(up2[i][j-1]!=-1) up2[i][j]=up2[up2[i][j-1]][j-1];
      else up2[i][j]=-1;
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  ll a=A;
  ll b=B;
  ll c=C;
  ll d=D;
  ll mx=rmax(c, d);
  // cout<<"mx: "<<mx<<'\n';
  ll tep=f2(a, b, mx);
  // cout<<"tep: "<<tep<<'\n';
  if(tep==b){
    return -1;
  }
  ll f, s;
  if(tep==-1){
    tep=a;
  }
  else{
    tep++;
  }
  ll mx2=rmax(tep, b);
  f=id[mx2];
  ll mx3=rmax(tep, c-1);
  s=f1(c, d, mx3);
  if(s==-1){
    return -1;
  }
  ll ans=0;
  ll cur=f;
  for(ll i=LOG-1;i>=0;i--){
    if(up1[cur][i]==-1) continue;
    if(h[up1[cur][i]]<=h[s]){
      cur=up1[cur][i];
      ans+=(1LL<<i);
    }
  }
  for(ll i=LOG-1;i>=0;i--){
    if(up2[cur][i]==-1) continue;
    if(h[up2[cur][i]]<=h[s]){
      cur=up2[cur][i];
      ans+=(1LL<<i);
    }
  }
  return (int) ans;
}

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