Submission #1213653

#TimeUsernameProblemLanguageResultExecution timeMemory
1213653lrnnzRainforest Jumps (APIO21_jumps)C++20
23 / 100
4072 ms155596 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> #include "jumps.h" using namespace std; #define all(a) (a).begin(), (a).end() #define sz(a) (int)(a).size() #define ll long long #define ld long double #define ui uint64_t #define cont(set, element) ((set).find(element) != (set).end()) /********* DEBUG *********/ template <typename T> void outvec(const vector<T>& Z){ for (const T& x : Z) cout << x << ' '; cout << "\n"; } void printVariable(const any& var) { if (!var.has_value()) { cout << "null"; return; } if (var.type() == typeid(int)) { cout << any_cast<int>(var); } else if (var.type() == typeid(double)) { cout << any_cast<double>(var); } else if (var.type() == typeid(float)) { cout << any_cast<float>(var); } else if (var.type() == typeid(char)) { cout << any_cast<char>(var); } else if (var.type() == typeid(bool)) { cout << (any_cast<bool>(var) ? "true" : "false"); } else if (var.type() == typeid(string)) { cout << any_cast<string>(var); } else if (var.type() == typeid(const char*)) { cout << any_cast<const char*>(var); } else if (var.type() == typeid(long long)) { cout << any_cast<long long>(var); } else { cout << "[unknown type]"; } } template<typename... Args> void outval(Args... args) { vector<any> variables = {args...}; for (size_t i = 0; i < variables.size(); ++i) { printVariable(variables[i]); if (i != variables.size() - 1) { cout << " "; } } cout << "\n"; } #define sp << " " << /********* DEBUG *********/ const ll MOD = 1000000007; const ll MOD2 = 998244353; const ll inf = 1e18; const ll mxN = 2000005; vector<ll> heights(mxN); ll n; vector<ll> pref(mxN), suff(mxN); const ll LOGN = 22; ll jumpR[mxN][LOGN], jumpL[mxN][LOGN]; ll realJump[mxN][LOGN]; void init(int N, vector<int> H) { n=N; heights.resize(n); pref.resize(n); suff.resize(n); for (int i = 0; i < n; i++) heights[i] = H[i]; // [height, idx] stack<pair<ll, ll>> st; for (int i = 0; i < n; i++){ while (st.size() && st.top().first < heights[i]) st.pop(); if (st.empty()) pref[i] = -1; else pref[i] = st.top().second; st.push({heights[i], i}); } while(st.size()) st.pop(); for (int i = n-1; i >= 0; i--){ while (st.size() && st.top().first < heights[i]) st.pop(); if (st.empty()) suff[i] = -1; else suff[i] = st.top().second; st.push({heights[i], i}); } // outvec(pref); // outvec(suff); for (int i = 0; i < LOGN; i++){ for (int j = 0; j < n; j++){ if (i == 0) jumpR[j][i] = suff[j]; else if (jumpR[j][i-1] != -1) jumpR[j][i] = jumpR[ jumpR[j][i-1] ][ i-1 ]; else jumpR[j][i] = -1; } } for (int i = 0; i < LOGN; i++){ for (int j = n-1; j >= 0; j--){ if (i == 0) jumpL[j][i] = pref[j]; else if (jumpL[j][i-1] != -1) jumpL[j][i] = jumpL[ jumpL[j][i-1] ][ i-1 ]; else jumpL[j][i] = -1; } } for (int i = 0; i < LOGN; i++){ for (int j = 0; j < n; j++){ if (i == 0){ if (suff[j] == -1 && pref[j] == -1) realJump[j][i] = -1; if (suff[j] == -1) realJump[j][i] = pref[j]; else if (pref[j] == -1) realJump[j][i] = suff[j]; else realJump[j][i] = heights[suff[j]] > heights[pref[j]] ? suff[j] : pref[j]; } else if (realJump[j][i-1] != -1) realJump[j][i] = realJump[ realJump[j][i-1] ][ i-1 ]; else realJump[j][i] = -1; } } } // subtask 5 int minimum_jumps(int A, int B, int C, int D) { ll curr = A, moves = 0; ll hi = heights[C], hiIdx = C; for (int i = C + 1; i <= D; i++){ if (heights[i] > hi) hiIdx = i, hi = heights[i]; } ll lhi = -1; for (int i = A; i <= B; i++){ if (heights[i] > lhi && heights[i] < hi) lhi = heights[i], curr = i; } if (lhi == -1) return -1; for (int i = C; i <= D; i++){ if (heights[i] > heights[curr]){ C = i; break; } } if (heights[curr] > heights[C]) return -1; for (int i = LOGN-1; i >= 0; i--){ if (realJump[curr][i] == -1) continue; if (heights[ realJump[curr][i] ] <= heights[C]){ curr = realJump[curr][i]; moves += (1 << i); } } for (int i = LOGN-1; i >= 0; i--){ if (jumpR[curr][i] == -1) continue; if (heights[ jumpR[curr][i] ] <= heights[C]){ curr = jumpR[curr][i]; moves += (1 << i); if (curr == C) break; } } return curr == C ? moves : -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...