oj.uz

Submission #649593

# Submission time Handle Problem Language Result Execution time Memory
649593 2022-10-11T02:41:30 Z alvinpiter Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 1689 ms 36404 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 221 ms 28480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 312 ms 16452 KB Output is correct
5 Correct 607 ms 35516 KB Output is correct
6 Correct 611 ms 6072 KB Output is correct
7 Correct 1105 ms 35480 KB Output is correct
8 Correct 620 ms 12368 KB Output is correct
9 Correct 1149 ms 35492 KB Output is correct
10 Correct 1439 ms 35616 KB Output is correct
11 Correct 1216 ms 35644 KB Output is correct
12 Correct 1494 ms 35552 KB Output is correct
13 Correct 1115 ms 35528 KB Output is correct
14 Correct 1603 ms 35940 KB Output is correct
15 Correct 1034 ms 36256 KB Output is correct
16 Correct 830 ms 36252 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 3 ms 240 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 3 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 18 ms 592 KB Output is correct
28 Correct 22 ms 592 KB Output is correct
29 Correct 21 ms 592 KB Output is correct
30 Correct 21 ms 592 KB Output is correct
31 Correct 19 ms 592 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 50 ms 20588 KB Output is correct
34 Correct 85 ms 35492 KB Output is correct
35 Correct 75 ms 35660 KB Output is correct
36 Correct 82 ms 35520 KB Output is correct
37 Correct 85 ms 35928 KB Output is correct
38 Correct 75 ms 36404 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 312 ms 16452 KB Output is correct
5 Correct 607 ms 35516 KB Output is correct
6 Correct 611 ms 6072 KB Output is correct
7 Correct 1105 ms 35480 KB Output is correct
8 Correct 620 ms 12368 KB Output is correct
9 Correct 1149 ms 35492 KB Output is correct
10 Correct 1439 ms 35616 KB Output is correct
11 Correct 1216 ms 35644 KB Output is correct
12 Correct 1494 ms 35552 KB Output is correct
13 Correct 1115 ms 35528 KB Output is correct
14 Correct 1603 ms 35940 KB Output is correct
15 Correct 1034 ms 36256 KB Output is correct
16 Correct 830 ms 36252 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 3 ms 240 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 3 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 18 ms 592 KB Output is correct
28 Correct 22 ms 592 KB Output is correct
29 Correct 21 ms 592 KB Output is correct
30 Correct 21 ms 592 KB Output is correct
31 Correct 19 ms 592 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 50 ms 20588 KB Output is correct
34 Correct 85 ms 35492 KB Output is correct
35 Correct 75 ms 35660 KB Output is correct
36 Correct 82 ms 35520 KB Output is correct
37 Correct 85 ms 35928 KB Output is correct
38 Correct 75 ms 36404 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 0 ms 208 KB Output is correct
42 Correct 279 ms 16336 KB Output is correct
43 Correct 1046 ms 35512 KB Output is correct
44 Correct 755 ms 6096 KB Output is correct
45 Correct 1033 ms 35512 KB Output is correct
46 Correct 439 ms 12368 KB Output is correct
47 Correct 1035 ms 35480 KB Output is correct
48 Correct 1689 ms 35576 KB Output is correct
49 Correct 1535 ms 35628 KB Output is correct
50 Correct 1440 ms 35564 KB Output is correct
51 Correct 1062 ms 35508 KB Output is correct
52 Correct 1494 ms 35932 KB Output is correct
53 Correct 1077 ms 36296 KB Output is correct
54 Correct 700 ms 36372 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Incorrect 154 ms 35364 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 221 ms 28480 KB Output isn't correct
4 Halted 0 ms 0 KB -