Submission #1202976

#TimeUsernameProblemLanguageResultExecution timeMemory
1202976lrnnzRainforest Jumps (APIO21_jumps)C++20
21 / 100
4032 ms44256 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 nl "\n" #define sp << " " << /********* DEBUG *********/ const ll MOD = 1000000007; const ll inf = 1e18; const ll mxN = 2000005; vector<int> heights(mxN); int n; // offline queries yeehaw /* Need 1: check if node x reachable from node y Solution: range max query them Need 2: min steps to reach node y Solution: create tree like structure, subtract depths Need 3: handle range queries Solution: idk */ vector<ll> pref(mxN), suff(mxN); 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); } // subtask 5 int minimum_jumps(int A, int B, int C, int D) { ll peak = 0; for (int i = C; i <= D; i++){ peak = max(peak, (ll)heights[i]); } vector<int> vis(n, -1); ll ans = INT_MAX; for (int i = B; i >= A; i--){ ll ptr = i, moves = 0; bool reach = false; while (true){ //outval("ptr:",ptr); if (vis[ptr] != -1 && moves > vis[ptr]) break; vis[ptr] = moves; bool flag = false; ll hl = pref[ptr] == -1 ? -1 : heights[pref[ptr]]; ll hr = suff[ptr] == -1 ? -1 : heights[suff[ptr]]; if (hl > peak) hl = -1; if (hr > peak) hr = -1; //outval("hl,hr:",hl,hr); if (hr != -1 && (hr > hl || (suff[ptr] >= C && suff[ptr] <= D))) ptr = suff[ptr], moves++, flag = true; else if (hl != -1 && hl > hr) ptr = pref[ptr], moves++, flag = true; if (ptr >= C && ptr <= D){ reach = true; break; } if (!flag) break; } if (reach) ans = min(ans, moves); } return ans == INT_MAX ? -1 : ans; }
#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...