Submission #1200077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200077		ackhava	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	2785 ms	99956 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(int i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;

vector<int> h;
vector<int> lm;
vector<int> rm;
int n;

int arr[200100][30];
int jmp[200100][30];
int lmp[200100][30];
int rmp[200100][30];

void init(int N, std::vector<int> H) {
  h=H;
  n=N;
  vector<pair<int,int>> stck;
  lm.clear(),rm.clear();
  REP(i,0,N){
    while(stck.size() && stck.back().fi < H[i])stck.pop_back();
    lm.pb(-1);
    if(stck.size())lm.back() = (stck.back().se);
    stck.pb({h[i],i});
  }
  stck.clear();
  REP(ix,0,N){
    auto i=N-1-ix;
    while(stck.size() && stck.back().fi < H[i])stck.pop_back();
    rm.pb(-1);
    if(stck.size())rm.back() = (stck.back().se);
    stck.pb({h[i],i});
  }
  reverse(rm.begin(),rm.end());
  memset(arr,-1,sizeof arr);
  memset(jmp,-1,sizeof jmp);
  memset(lmp,-1,sizeof lmp);
  memset(rmp,-1,sizeof rmp);
  REP(i,0,N){
    arr[i][0]=h[i];
    lmp[i][0]=lm[i];
    rmp[i][0]=rm[i];
    int lc=-1,rc=-1;
    if(lm[i]!=-1)lc=h[lm[i]];
    if(rm[i]!=-1)rc=h[rm[i]];
    if(lc > rc)jmp[i][0]=lm[i];
    else if(rc > lc)jmp[i][0]=rm[i];
  }
  REP(j,1,30){
    REP(i,0,N){
      if((i+(1<<(j-1)))<N)arr[i][j]=max(arr[i][j-1],arr[i+(1<<(j-1))][j-1]);
      if(jmp[i][j-1]!=-1)jmp[i][j]=jmp[jmp[i][j-1]][j-1];
      if(lmp[i][j-1]!=-1)lmp[i][j]=lmp[lmp[i][j-1]][j-1];
      if(rmp[i][j-1]!=-1)rmp[i][j]=rmp[rmp[i][j-1]][j-1];
    }
  }
}

int query(int x, int y){
  int dist=y-x+1;
  dist|=dist>>1;
  dist|=dist>>2;
  dist|=dist>>3;
  dist|=dist>>4;
  dist|=dist>>7;
  dist|=dist>>8;
  dist|=dist>>15;
  dist|=dist>>16;
  dist|=dist>>31;
  dist++;
  auto b=__builtin_ctz(dist)-1;
  return max(arr[x][b],arr[y-(1<<b)+1][b]);
}

int minimum_jumps(int A, int B, int C, int D) {
  // int mx=query(C,D);
  int mx=0;
  REP(i,C,D+1)mx=max(h[i],mx);
  int b=B;
  if(h[b]>mx)return -1;
  REP(ix,0,25){
    auto i=24-ix;
    if(lmp[b][i]!=-1 && h[lmp[b][i]]<mx && lmp[b][i]>=A)b=lmp[b][i];
  }
  int ans=1;
  auto valid = [&](int x){
    return x!=-1 && h[x]<=mx && !(C <= rm[x] && rm[x] <= D) && !(C <= x && x <= D);
  };
  // cerr<<"SELECT "<<b<<endl;
  if(b==-1){return -1;}
  REP(ix,0,25){
    auto i=24-ix;
    if((C <= rm[b] && rm[b] <= D) || (C <= b && b <= D))break;
    if(valid(jmp[b][i]))b=jmp[b][i],ans+=1<<i,cerr<<b<<" "<<ans<<endl;
    if((C <= rm[b] && rm[b] <= D) || (C <= b && b <= D))break;
  }
  REP(ix,0,25){
    auto i=24-ix;
    if((C <= rm[b] && rm[b] <= D) || (C <= b && b <= D))break;
    if(valid(lmp[b][i]))b=lmp[b][i],ans+=1<<i,cerr<<b<<" "<<ans<<endl;
    if((C <= rm[b] && rm[b] <= D) || (C <= b && b <= D))break;
    if(valid(rmp[b][i]))b=rmp[b][i],ans+=1<<i,cerr<<b<<" "<<ans<<endl;
    if((C <= rm[b] && rm[b] <= D) || (C <= b && b <= D))break;
  }
  if(C <= b && b <= D)return ans-1;
  if(C <= rm[b] && rm[b] <= D)return ans;
  if(C <= rm[lm[b]] && rm[lm[b]] <= D)return ans+1;
  if(C <= rm[rm[b]] && rm[rm[b]] <= D)return ans+1;
  assert(h[C]<=mx);
  REP(i,B,C)if(h[i]>mx)return -1;
  return -1;
}

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