Submission #1213632

#TimeUsernameProblemLanguageResultExecution timeMemory
1213632lrnnzRainforest Jumps (APIO21_jumps)C++20
48 / 100
663 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) { int curr = B, moves = 0; ll Rcurr = C; for (int i = LOGN-1; i >= 0; i--){ if (jumpR[Rcurr][i] == -1) continue; if (jumpR[Rcurr][i] <= D) Rcurr = jumpR[Rcurr][i]; } for (int i = LOGN-1; i >= 0; i--){ if (jumpL[curr][i] == -1) continue; if (jumpL[curr][i] >= A && heights[jumpL[curr][i]] <= heights[Rcurr]) curr = jumpL[curr][i]; } Rcurr = C; while (true){ if (heights[Rcurr] > heights[curr]) break; if (jumpR[Rcurr][0] <= D) Rcurr = jumpR[Rcurr][0]; else break; } C = Rcurr; if (heights[curr] > heights[C]) return -1; //outval("C:",C); 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...