Submission #572374

#	Time	Username	Problem	Language	Result	Execution time	Memory
572374		600Mihnea	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1464 ms	84056 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 200000 + 7;
const int K = 20;
const int inf = (int) 1e9 + 7;
int n, a[N], lft[N], rgh[N], position[N], go[N], mn[N], mx[N], jump_mx[K][N], jump_rgh[K][N], max_pos[K][N], max_pos2[K][N];
int rmq[K][N], lg2[N];

int getmax(int l, int r) {
  assert(1 <= l && l <= r && r <= n);
  int k = lg2[r - l + 1];
  return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

void init(int nn, vector<int> hh) {
  n = nn;

  assert(n == (int) hh.size());

  for (int i = 1; i <= n; i++) {
    a[i] = hh[i - 1];
    position[a[i]] = i;

    rmq[0][i] = a[i];
  }

  for (int i = 2; i <= n; i++) {
    lg2[i] = 1 + lg2[i / 2];
  }

  for (int k = 1; (1 << k) <= n; k++) {
    for (int i = 1; i + (1 << k) - 1 <= n; i++) {
      rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
    }
  }


  {
    vector<int> stk;
    for (int i = 1; i <= n; i++) {
      while (!stk.empty() && a[stk.back()] <= a[i]) stk.pop_back();
      if (!stk.empty()) lft[i] = stk.back(); else lft[i] = 0;
      stk.push_back(i);
    }
  }
  {
    vector<int> stk;
    for (int i = n; i >= 1; i--) {
      while (!stk.empty() && a[stk.back()] <= a[i]) stk.pop_back();
      if (!stk.empty()) rgh[i] = stk.back(); else rgh[i] = 0;
      stk.push_back(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (lft[i]) {
      assert(a[lft[i]] > a[i]);
    }
    if (rgh[i]) {
      assert(a[rgh[i]] > a[i]);
    }
  }

  for (int i = 1; i <= n; i++) {
    go[i] = i;
    if (lft[i] && a[lft[i]] > a[go[i]]) go[i] = lft[i];
    if (rgh[i] && a[rgh[i]] > a[go[i]]) go[i] = rgh[i];
  }

  for (int i = 1; i <= n; i++) {
    if (lft[i] == 0 && rgh[i] == 0) {
      mn[i] = lft[i] = 0;
      continue;
    }
    if (lft[i] == 0) {
      mn[i] = mx[i] = rgh[i];
      continue;
    }
    if (rgh[i] == 0) {
      mn[i] = mx[i] = lft[i];
      continue;
    }
    if (a[lft[i]] < a[rgh[i]]) {
      mn[i] = lft[i];
      mx[i] = rgh[i];
    } else {
      mn[i] = rgh[i];
      mx[i] = lft[i];
    }
  }

  for (int i = 0; i <= n; i++) {
    jump_mx[0][i] = mx[i];
    jump_rgh[0][i] = rgh[i];
    max_pos[0][i] = i;
    max_pos2[0][i] = mn[i];
  }

  a[0] = inf;

  for (int k = 1; k < K; k++) {
    for (int i = 0; i <= n; i++) {
      jump_mx[k][i] = jump_mx[k - 1][jump_mx[k - 1][i]];
      max_pos[k][i] = max(max_pos[k - 1][i], max_pos[k - 1][jump_mx[k - 1][i]]);
      max_pos2[k][i] = max(max_pos2[k - 1][i], max_pos2[k - 1][jump_mx[k - 1][i]]);
    }
  }

  for (int k = 1; k < K; k++) {
    for (int i = 0; i <= n; i++) {
      jump_rgh[k][i] = jump_rgh[k - 1][jump_rgh[k - 1][i]];
    }
  }
}

int minimum_jumps(int l1, int r1, int l2, int r2) {
  l1++;
  r1++;
  l2++;
  r2++;

  assert(1 <= l1 && l1 <= r1 && r1 < l2 && l2 <= r2 && r2 <= n);

  int ymax = getmax(l2, r2);
  l1 = max(l1, lft[position[ymax]] + 1);

  if (l1 > r1) {
    return -1;
  }

  int x = position[getmax(l1, r1)];
  int p = x;
  int max_steps = 0;
  int stop1 = 0;
  int stop2 = 0;

  {
    p = x;
    for (int k = K - 1; k >= 0; k--) {
      if (a[jump_mx[k][p]] <= ymax) {
        max_steps += (1 << k);
        p = jump_mx[k][p];
      }
    }
  }

  {
    p = x;
    for (int k = K - 1; k >= 0; k--) {
      if (max_pos[k][p] < l2) {
        p = jump_mx[k][p];
        stop1 += (1 << k);
      }
    }
  }
  {
    p = x;
    for (int k = K - 1; k >= 0; k--) {
      if (max_pos2[k][p] < l2) {
        p = jump_mx[k][p];
        stop2 += (1 << k);
      }
    }
  }
  p = x;

  if (stop1 < max_steps && stop2 < max_steps) {
    return min(stop1, stop2 + 1);
  }

  if (stop1 < max_steps) {
    return stop1;
  }

  if (stop2 < max_steps) {
    return stop2 + 1;
  }


  p = x;
  {
    for (int k = 0; k < K; k++) {
      if (max_steps & (1 << k)) {
        p = jump_mx[k][p];
      }
    }
  }
  if (l2 <= p && p <= r2) {
    return max_steps;
  }


  int ret = max_steps + 1;
  for (int k = K - 1; k >= 0; k--) {
    if (jump_rgh[k][p] != 0 && jump_rgh[k][p] < l2) {
      p = jump_rgh[k][p];
      ret += (1 << k);
    }
  }
  return ret;

}

• 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