Submission #649593

#	Time	Username	Problem	Language	Result	Execution time	Memory
649593		alvinpiter	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	1689 ms	36404 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 200000
#define MAXH 200000
#define MAXLG 17

int n, prevHigher[MAXN + 3], nextHigher[MAXN + 3], highest[MAXH + 3][MAXLG + 3], secondHighest[MAXH + 3][MAXLG + 3];
vector<int> h;

void initPrevHigher() {
  stack<int> stHeight;
  for (int i = 0; i < n; i++) {
    while (!stHeight.empty() && h[i] > stHeight.top()) {
      stHeight.pop();
    }

    prevHigher[i] = (stHeight.empty() ? INF : stHeight.top());
    stHeight.push(h[i]);
  }
}

void initNextHigher() {
  stack<int> stHeight;
  for (int i = n - 1; i >= 0; i--) {
    while (!stHeight.empty() && h[i] > stHeight.top()) {
      stHeight.pop();
    }

    nextHigher[i] = (stHeight.empty() ? INF : stHeight.top());
    stHeight.push(h[i]);
  }
}

void initHighestAndSecondHighest() {
  for (int h = 1; h <= n; h++) {
    highest[h][0] = secondHighest[h][0] = INF;
  }

  for (int i = 0; i < n; i++) {
    highest[h[i]][0] = max(prevHigher[i], nextHigher[i]);
    secondHighest[h[i]][0] = min(prevHigher[i], nextHigher[i]);
  }

  for (int lg = 1; lg <= MAXLG; lg++) {
    for (int h = 1; h <= n; h++) {
      if (highest[h][lg - 1] < INF) {
        highest[h][lg] = highest[highest[h][lg - 1]][lg - 1];
      } else {
        highest[h][lg] = INF;
      }

      if (secondHighest[h][lg - 1] < INF) {
        secondHighest[h][lg] = secondHighest[secondHighest[h][lg - 1]][lg - 1];
      } else {
        secondHighest[h][lg] = INF;
      }
    }
  }
}

int getLastHeightFollowingHighest(int startingHeight, int numJumps) {
  int currentHeight = startingHeight;
  for (int lg = 0; lg <= MAXLG && currentHeight < INF; lg++) {
    if (numJumps & (1 << lg)) {
      currentHeight = highest[currentHeight][lg];
    }
  }

  return currentHeight;
}

int getLastHeightFollowingSecondHighest(int startingHeight, int numJumps) {
  int currentHeight = startingHeight;
  for (int lg = 0; lg <= MAXLG && currentHeight < INF; lg++) {
    if (numJumps & (1 << lg)) {
      currentHeight = secondHighest[currentHeight][lg];
    }
  }

  return currentHeight;
}

void init(int N, std::vector<int> H) {
  n = N;
  h = H;

  initPrevHigher();
  initNextHigher();
  initHighestAndSecondHighest();

  // cout << "\nprevHigher\n";
  // for (int i = 0; i < n; i++) {
  //   cout << prevHigher[i] << endl;
  // }

  // cout << "\nnextHigher\n";
  // for (int i = 0; i < n; i++) {
  //   cout << nextHigher[i] << endl;
  // }

  // cout << endl;
  // for (int i = 1; i <= 3; i++) {
  //   cout << "highest[" << i << "]: " << highest[i][0] << endl;
  //   cout << "secondHighest[" << i << "]: " << secondHighest[i][0] << endl;
  // }
}

int minimum_jumps(int A, int B, int C, int D) {
  int startingHeight = h[A];

  // cout << "\nstartingHeight: " << startingHeight << endl;

  // Calculate max number of jumps if we follow the highest pointer
  int numHighestJumps;
  if (true) {
    int lo = 0, hi = MAXN, mid;
    while (hi >= lo) {
      mid = (lo + hi)/2;
      if (getLastHeightFollowingHighest(startingHeight, mid) <= h[C]) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }

    numHighestJumps = hi;
  }

  // cout << "\nnumHighestJumps: " << numHighestJumps << endl;

  int heightAfterFollowingHighest = getLastHeightFollowingHighest(startingHeight, numHighestJumps);
  // cout << "\nheight after following highest:" << heightAfterFollowingHighest << endl;

  // Calculate max number of jumps if we follow the second highest pointer
  int numSecondHighestJumps;
  if (true) {
    int lo = 0, hi = MAXN, mid;
    while (hi >= lo) {
      mid = (lo + hi)/2;
      if (getLastHeightFollowingSecondHighest(heightAfterFollowingHighest, mid) <= h[C]) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }

    numSecondHighestJumps = hi;
  }

  int finalHeight = getLastHeightFollowingSecondHighest(heightAfterFollowingHighest, numSecondHighestJumps);
  // cout << "numSecondHighestJumps: " << numSecondHighestJumps << endl;
  // cout << "finalHeight: " << finalHeight << endl;

  if (finalHeight == h[C]) {
    return numHighestJumps + numSecondHighestJumps;
  } 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