Submission #1052647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052647		kachim2	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	907 ms	49996 KiB

jumps

#include "jumps.h"
//#include "stub.cpp"
#include<queue>
#include<array>
#include <vector>
#include <iostream>
using namespace std;
std::vector<int> H;
vector<int> nxt;
vector<int> prv;
vector<int> d;
array<pair<int, int>, 1<<20> segtree;
vector<array<int, 25>> jp;
vector<array<int, 25>> njp;
bool subtask1=1;
pair<int, int> mquery(int a, int b){
  a--;
  b++;
  a+=(segtree.size()/2)+1;
  b+=(segtree.size()/2)+1;
  pair<int, int> res = {0, 0};
  while(b-a > 1){
    if(a%2 == 0){
      res = max(segtree[a+1], res);
    }
    if(b%2 == 1){
      res = max(segtree[b-1], res);
    }
    a/=2;
    b/=2;
  }
  return res;
}


void init(int N, std::vector<int> nH)
{
  for(int i = 0; i < N; i++){
    if(nH[i]!=i+1) subtask1=0;
  }
  H = nH;
  
  nxt.resize(N);
  prv.resize(N);
  jp.resize(N);
  njp.resize(N);
  {
  vector<int> kmon;
  for (int i = 0; i < N; i++)
  {
    if (kmon.empty())
    {
      kmon.push_back(i);
      prv[i] = -1;
      continue;
    }
    while (H[kmon.back()] < H[i])
    {
      kmon.pop_back();
      if (kmon.empty())
      {
        kmon.push_back(i);
        prv[i] = -1;
        goto nd;
      }
    }
    prv[i] = kmon.back();
    kmon.push_back(i);
    nd:;
  }
  }
  {
  vector<int> kmon;
  for (int i = N-1; i>=0; i--)
  {
    if (kmon.empty())
    {
      kmon.push_back(i);
      nxt[i] = -1;
      continue;
    }
    while (H[kmon.back()] < H[i])
    {
      kmon.pop_back();
      if (kmon.empty())
      {
        kmon.push_back(i);
        nxt[i] = -1;
        goto nd2;
      }
    }
    nxt[i] = kmon.back();
    kmon.push_back(i);
    nd2:;
  }
  }
  
  for(int i = 0; i < N; i++){
    if(H[prv[i]]>H[nxt[i]]){
      jp[i][0] = prv[i]; 
    }else if (H[prv[i]]<H[nxt[i]]){
      jp[i][0] = nxt[i];
    }else{
      jp[i][0] = -1;
    }
  }
  for(int j = 1; j < jp[0].size(); j++){
    for(int i = 0; i < N; i++){
      if(jp[i][j-1] != -1) 
      jp[i][j] = jp[jp[i][j-1]][j-1];
      else jp[i][j] = -1;
    }
  }
  for(int i = 0; i < N; i++){
    njp[i][0] = nxt[i];
  }
  for(int j = 1; j < njp[0].size(); j++){
    for(int i = 0; i < N; i++){
      if(njp[i][j-1] != -1) 
      njp[i][j] = njp[njp[i][j-1]][j-1];
      else njp[i][j] = -1;
    }
  }
  for(int i = 0; i < N; i++){
    segtree[i+(segtree.size()/2)+1].first = H[i];
    segtree[i+(segtree.size()/2)+1].second = i;
  }
  for(int i =  segtree.size()/2-1; i>=1; i--){
    segtree[i] = max(segtree[i*2], segtree[i*2+1]);
  }
  

}

int minimum_jumps(int A, int B, int C, int D)
{
  if (subtask1) return C-B;
if( true){

int mxc = mquery(C, D).first;
int cur = -1;
if(H[B]> mxc) return -1;
{
int l = A, r = B;

while(l<=r){
const int mid = (l+r)/2;
int x = mquery(mid, B).first;
if(x>mxc){
  l = mid+1;
}else{
  r = mid-1;
  cur = mid;
}
}
if(cur == -1) return -1;
cur = mquery(cur, B).second;
if(mquery(cur, C-1).first > mxc) return -1;
}
int mmid = mquery(B+1, C-1).first;
int res=0;
for(int i = jp[0].size()-1; i>=0; i--){
  if(jp[cur][i]!=-1){
    if(H[jp[cur][i]] <= mmid){
      res+=1<<i;
      if(H[jp[cur][i]] == mmid) return res+1;
      cur = jp[cur][i];
      
    }
  }
}
if(nxt[cur] >= C) return res+1;
if(H[jp[cur][0]] < mxc)
return res+2;
for(int i = njp[0].size()-1; i>=0; i--){
  if(njp[cur][i]!=-1){
    if(njp[cur][i] < C){
      res+=1<<i;
      if(njp[cur][i] == C) return res;
      cur = njp[cur][i];
      
    }
  }
}

return res+1;
























}

  int mcd = 0;
  for (int i = C; i <= D; i++)
  {
    mcd = max(mcd, H[i]);
  }
  int bs = 0;
  for (int i = B; i >= A; i--)
  {
    // cerr << H[i] << ' ';
    if (H[i] < mcd)
      bs = max(bs, i);
    else
      break;
  }
  // cerr << bs << '\n';

  vector<bool> visited(H.size(), 0);

  queue<pair<int, int>> q;
  for(int i = A; i <=B; i++)
  q.push({i, 0});
  while(!q.empty()){
    auto x = q.front();
    q.pop();
    if(visited[x.first]) continue;
    visited[x.first] = 1;
    if(x.first >= C && x.first <= D) return x.second;
    if(nxt[x.first]!=-1) q.push({nxt[x.first], x.second+1});
    if(prv[x.first]!=-1) q.push({prv[x.first], x.second+1});
  }
  return -1;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 25>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int j = 1; j < jp[0].size(); j++){
      |                  ~~^~~~~~~~~~~~~~
jumps.cpp:117:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 25>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for(int j = 1; j < njp[0].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~

• 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