Submission #649615

#TimeUsernameProblemLanguageResultExecution timeMemory
649615alvinpiterRainforest Jumps (APIO21_jumps)C++17
48 / 100
1755 ms52108 KiB
#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) <= h[C]) { hi = mid - 1; } else { lo = mid + 1; } } if (lo > B) { return -1; } else { startingHeight = rangeMaxQuery(lo, B); } } // 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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...