Submission #1197937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197937		hengliao	밀림 점프 (APIO21_jumps)	C++20	100 / 100	1255 ms	161668 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;
  const ll inf=1e18;
  
  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 up3[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;
      up3[i][0]=-1;
      up2[i][0]=-1;
    }
    else if(f==-1){
      up1[i][0]=s;
      up3[i][0]=s;
      up2[i][0]=-1;
    }
    else if(s==-1){
      up1[i][0]=f;
      up3[i][0]=f;
      up2[i][0]=-1;
    }
    else{
      if(h[f]>h[s]){
        up1[i][0]=f;
        up3[i][0]=f;
        up2[i][0]=s;
      }
      else{
        up1[i][0]=s;
        up3[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];
        if(up3[up1[i][j-1]][j-1]==-1){
          up3[i][j]=-1;
        }  
        else{
          up3[i][j]=max(up3[i][j-1], up3[up1[i][j-1]][j-1]);
        }    
      }
      else{
        up1[i][j]=-1;
        up3[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(0, b, mx);
  // cout<<"tep: "<<tep<<'\n';
  if(tep==b){
    return -1;
  }
  ll f, s;
  if(tep==-1){
    tep=0;
  }
  else{
    tep++;
  }
  ll mx2=rmax(max(tep, a), b);
  f=id[mx2];
  ll mx3=rmax(tep, c-1);
  s=f1(c, d, mx3);
  // cout<<"f s "<<f<<' '<<s<<'\n';
  if(s==-1){
    return -1;
  }
  ll re=inf;
  // for(ll tar=c;tar<=d;tar++){
  ll mxidx=f;
    ll ans=0;
    ll cur=f;
    ll cnt=0;
    for(ll i=LOG-1;i>=0;i--){
      if(up1[cur][i]==-1) continue;
      if(h[up1[cur][i]]<=h[s]){
        // mxidx=max(mxidx, up3[cur][i]);
        cur=up1[cur][i];
        ans+=(1LL<<i);
        cnt+=(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);
      }
    }
    cur=f;
    ll dick=0;
    for(ll i=LOG-1;i>=0;i--){
      if(up1[cur][i]==-1) continue;
      if(up3[cur][i]<c && h[up1[cur][i]]<=h[s]){
        mxidx=max(mxidx, up3[cur][i]);
        cur=up1[cur][i];
        dick+=(1LL<<i);
      }
    }
    if(up1[cur][0]!=-1){
      cur=up1[cur][0];
      if(cur>=c && cur<=d){
        dick++;
        ans=min(ans, dick);
      }
    }
    // cout<<"ans1 "<<ans<<'\n';
    // cout<<mxidx<<'\n';
  auto check=[&](ll tar){
    ll dumb=f;
    for(ll i=0;i<LOG;i++){
      if(tar&(1LL<<i)){
        if(up1[dumb][i]==-1) return false;
        dumb=up1[dumb][i];
      }
    }
    if(up2[dumb][0]>=c && up2[dumb][0]<=d){
      return true;
    }
    return false;
  };
  ll lef=0, rig=ans-1;
  while(lef<=rig){
    ll mid=(lef+rig)/2;
    if(check(mid)){
      ans=mid+1;
      rig=mid-1;
    }
    else{
      lef=mid+1;
    }
  }

  // cout<<"mxidx: "<<mxidx<<'\n';
  
  
  ll dumb2=rmax(mxidx, c-1);
  ll s2=f1(c, d, dumb2);
  
  // cout<<"s2: "<<s2<<'\n';
  if(s2!=-1){
    ll ans2=0;
    cur=f;
    for(ll i=LOG-1;i>=0;i--){
      if(up1[cur][i]==-1) continue;
      if(h[up1[cur][i]]<=h[s2]){
        // mxidxax(mxidx, up3[cur][i]);
        cur=up1[cur][i];
        ans2+=(1LL<<i);
      }
    }
    for(ll i=LOG-1;i>=0;i--){
      if(up2[cur][i]==-1) continue;
      if(h[up2[cur][i]]<=h[s2]){
        cur=up2[cur][i];
        ans2+=(1LL<<i);
      }
    }
    if(cur==s2){
      ans=min(ans, ans2);
    }
  }
  return (int) ans;
}

• 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