Submission #649620

#	Time	Username	Problem	Language	Result	Execution time	Memory
649620		alvinpiter	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1814 ms	51288 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];
int spTableMax[MAXN + 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 initSpTableMax() {
  for (int i = 0; i < n; i++) {
    spTableMax[i][0] = h[i];
  }

  for (int lg = 1; lg <= MAXLG; lg++) {
    for (int i = 0; i < n; i++) {
      if (i + (1 << (lg - 1)) < n) {
        spTableMax[i][lg] = max(spTableMax[i][lg - 1], spTableMax[i + (1 << (lg - 1))][lg - 1]);
      } else {
        spTableMax[i][lg] = spTableMax[i][lg - 1];
      }
    }
  }
}

int rangeMaxQuery(int a, int b) {
  int len = b - a + 1;
  int msb;
  for (int lg = MAXLG; lg >= 0; lg--) {
    if (len & (1 << lg)) {
      msb = lg;
      break;
    }
  }

  return max(spTableMax[a][msb], spTableMax[b + 1 - (1 << msb)][msb]);
}

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

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

  initSpTableMax();

  // 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) {
  // Find the best starting height
  int startingHeight;
  if (true) {
    int lo = A, hi = B, mid;
    while (hi >= lo) {
      mid = (lo + hi)/2;
      if (rangeMaxQuery(mid, B) <= rangeMaxQuery(C, D)) {
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }

    if (lo > B) {
      return -1;
    } else {
      startingHeight = rangeMaxQuery(lo, B);
    }
  }

  // Find the best ending height
  int endingHeight;
  if (true) {
    int lo = C, hi = D, mid;
    while (hi >= lo) {
      mid = (lo + hi)/2;
      if (rangeMaxQuery(C, mid) < startingHeight) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }

    endingHeight = rangeMaxQuery(C, lo);
  }

  // cout << "\nstartingHeight: " << startingHeight << endl;
  // cout << "\nendingHeight: " << endingHeight << 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) <= endingHeight) {
        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) <= endingHeight) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }

    numSecondHighestJumps = hi;
  }

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

  return numHighestJumps + numSecondHighestJumps;
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:219:7: warning: unused variable 'finalHeight' [-Wunused-variable]
  219 |   int finalHeight = getLastHeightFollowingSecondHighest(heightAfterFollowingHighest, numSecondHighestJumps);
      |       ^~~~~~~~~~~

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