Submission #1052659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052659		Piokemon	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	827 ms	55500 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;
}

vector<int> bloki;
bool rob=0;
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){
      if (rob) bloki.push_back(x);
        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));
}

int zejdz(int x, int cel){
  if (x>=base)return x-base;
  if (tree[2*x+1].first>=cel)return zejdz(2*x+1,cel);
  return zejdz(2*x,cel);
}

int zejdz2(int x, int cel){
  if (x>=base)return x-base;
  if (tree[2*x].first>=cel)return zejdz2(2*x,cel);
  return zejdz2(2*x+1,cel);
}

int dist(int pocz, int C, int D){
  int odp=0;
  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){
      //cerr << pocz << " ->r " << jmpr[pocz][0] << " koszt: 1\n";
      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){
      //cerr << pocz << " ->l " << jmpl[pocz][0] << " koszt: 1\n";
      odp++;
      pocz=jmpl[pocz][0];
    }
  }
  if (pocz==n)return 1e9;
  if (!(C<=pocz && pocz<=D)) return 1e9;
  return odp;
}

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= -1; // TODO
  rob=1;
  bloki.clear();
  int odp2=1e9;
  if (query(1,0,base-1,A,B).first<mid){
    rob=0;
    pocz=query(1,0,base-1,A,B).second;
  }
  else{
    if (A<C){
      for (int x=bloki.size()-1;x>=0;x--){
        if (tree[bloki[x]].first>=mid){
          pocz = zejdz(bloki[x],mid);
        }
      }
      odp2 = dist(pocz,C,D);
      if (pocz!=B)pocz=query(1,0,base-1,pocz+1,B).second;
    }
    else{
      for (int x=0;x<bloki.size();x++){
        if (tree[bloki[x]].first>=mid){
          pocz = zejdz2(bloki[x],mid);
        }
      }
      odp2=dist(pocz,C,D);
      if (pocz!=A)pocz=query(1,0,base-1,A,pocz-1).second;
    }
  }
  rob=0;
  //cerr << mid << ' ' << pocz << '\n';
  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 << " ->h " << jmp[pocz][0] << " koszt: 1\n";
    pocz=jmp[pocz][0];
    odp++;
  }
  odp+=dist(pocz,C,D);
  //cerr << odp << ' ' << odp2 << '\n';
  if (min(odp,odp2)==1e9) return -1;
  return min(odp,odp2);
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:150:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |       for (int x=0;x<bloki.size();x++){
      |                    ~^~~~~~~~~~~~~

• 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