Submission #1052598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052598		Piokemon	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	173 ms	37984 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 2e5;
constexpr int K = 18;
int jmp[N+9][K+1];
int last[N+9][K+1];
int h[N+9];
int l[N+9];
int r[N+9];
int dst[N+9];
int n;
constexpr int base = (1<<18);
pair<int,int> tree[2*base+9];
// min

pair<int,int> bet(pair<int,int> a, pair<int,int> b){
  if (a.first>b.first)return a;
  else return b;
}

pair<int,int> query(int x, int a, int b, int p, int k){
    if (b<p || k<a)return {-1,0};
    if (p<=a && b<=k){
        return tree[x];
    }
    int mid=(a+b)/2;
    return bet(query(2*x,a,mid,p,k),query(2*x+1,mid+1,b,p,k));
}

void init(int N, std::vector<int> H) {
    n=N;
    for (int x=0;x<n;x++)h[x]=H[x];
    vector<pair<int,int>> stos; stos.push_back({2e9,n});
    for (int x=0;x<n;x++){
      while(h[x]>stos.back().first)stos.pop_back();
      l[x]=stos.back().second;
      stos.push_back({h[x],x});
    }
    h[n]=-2e9;
    stos.clear(); stos.push_back({2e9,n});
    for (int x=n-1;x>=0;x--){
      while(h[x]>stos.back().first)stos.pop_back();
      r[x]=stos.back().second;
      stos.push_back({h[x],x});
    }
    for (int x=base;x<base+n;x++)tree[x]={h[x-base],x-base};
    for (int x=base-1;x>=1;x--)tree[x]=bet(tree[2*x],tree[2*x+1]);
    for (int x=0;x<n;x++){
      if (h[l[x]]>h[r[x]])jmp[x][0]=l[x];
      else jmp[x][0]=r[x];
      last[x][0]=max(x,jmp[x][0]);
    }
    jmp[n][0]=n; last[n][0]=n;
    for (int k=1;k<=K;k++){
      for (int x=0;x<=n;x++){
        jmp[x][k]=jmp[jmp[x][k-1]][k-1];
        last[x][k]=max(last[x][k-1],last[jmp[x][k-1]][k-1]);
      }
    }
    /*for (int x=0;x<n;x++){
      cerr << l[x] << ' ' << r[x] << '\n';
    }*/
    return;
}

int minimum_jumps(int A, int B, int C, int D){
  if (C<=B && B<=D)return 0;
  if (C<=A && A<=D)return 0;
  if (A<=C && D<=B)return 0;
  int mid=0;
  if (C-B>1)mid=query(1,0,base-1,B+1,C-1).first;
  if (A-D>1)mid=query(1,0,base-1,D+1,A-1).first;
  int pocz= A; // TODO
  int odp=0;
  for (int k=K;k>=0;k--){
    if (last[pocz][k]<C){
      odp+=(1<<k);
      pocz=jmp[pocz][k];
    }
  }
  while ((!(C<=pocz && pocz <= D)) && pocz!=n){
    pocz=jmp[pocz][0];
    odp++;
  }
  if (C<=pocz && pocz<=D) return odp;
  else return -1;
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:73:7: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
   73 |   int mid=0;
      |       ^~~

• Subtask 1: 0 / 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