Submission #1052629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052629		Piokemon	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	706 ms	55496 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 jmpl[N+9][K+1];
int jmpr[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];
      jmpl[x][0]=l[x];
      jmpr[x][0]=r[x];
    }
    jmp[n][0]=n;jmpl[n][0]=n; jmpr[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];
        jmpl[x][k]=jmpl[jmpl[x][k-1]][k-1];
        jmpr[x][k]=jmpr[jmpr[x][k-1]][k-1];
      }
    }
    //for (int x=0;x<n;x++) cerr << jmp[x][0] << ' ';
    //cerr << '\n';
    /*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;
  int kon = query(1,0,base-1,C,D).first;
  for (int k=K;k>=0;k--){
    if (h[jmp[pocz][k]]<mid && h[jmp[pocz][k]]!=-2e9 && h[jmp[pocz][k]]<=kon){
      //cerr << pocz << " ->h " << jmp[pocz][k] << " koszt: " << (1<<k) << '\n';
      odp+=(1<<k);
      pocz=jmp[pocz][k];
    }
  }
  while (h[pocz]<mid && pocz!=n && h[jmp[pocz][0]]<=kon){
    //cerr << pocz << " -> " << jmp[pocz][0] << " koszt: 1\n";
    pocz=jmp[pocz][0];
    odp++;
  }
  if (pocz<C){
    for (int k=K;k>=0;k--){
      if (jmpr[pocz][k]<C){
         //cerr << pocz << " ->r " << jmpr[pocz][k] << " koszt: " << (1<<k) << '\n';
        odp+=(1<<k);
        pocz=jmpr[pocz][k];
      }
    }
    while(pocz<C){
      odp++;
      pocz=jmpr[pocz][0];
    }
  }
  if (pocz>D){
    for (int k=K;k>=0;k--){
      if (jmpl[pocz][k]>D && jmpl[pocz][k]!=n){
         //cerr << pocz << " ->l " << jmpl[pocz][k] << " koszt: " << (1<<k) << '\n';
        odp+=(1<<k);
        pocz=jmpl[pocz][k];
      }
    }
    while(pocz>D && pocz!=n){
      odp++;
      pocz=jmpl[pocz][0];
    }
  }
  if (C<=pocz && pocz<=D) return odp;
  else return -1;
}

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