Submission #1165032

#TimeUsernameProblemLanguageResultExecution timeMemory
1165032baldwin_huangRainforest Jumps (APIO21_jumps)C++20
0 / 100
4046 ms19088 KiB
#include <bits/stdc++.h> using namespace std; int n; const int INF = 1e9; struct node { int left = -1; int right = -1; }; vector<node> nodes; void init(int N, vector<int> H) { n = N; nodes = vector<node>(n); // Precomputing the left value. set<int> heights_l; vector<int> last_val_l(n + 1, -1); for (int i = 0; i < n; i++) { auto it = heights_l.upper_bound(H[i]); if (it != heights_l.end()) { nodes[i].left = last_val_l[*it]; } heights_l.insert(H[i]); last_val_l[H[i]] = i; } // Precomputing the right values. set<int> heights_r; vector<int> last_val_r(n + 1, -1); for (int i = n - 1; i >= 0; i--) { auto it = heights_r.upper_bound(H[i]); if (it != heights_r.end()) { nodes[i].right = last_val_r[*it]; } heights_r.insert(H[i]); last_val_r[H[i]] = i; } // for (int i = 0; i < n; i++) { // cout << "Node " << i << ": " << nodes[i].left << ' ' << nodes[i].right << '\n'; // } return; } int minimum_jumps(int A, int B, int C, int D) { // Start the BFS vector<int> dist(n, INF); queue<int> q; // cout << A << ' ' << B << ' ' << nodes.size() << '\n'; for (int i = A; i <= B; i++) { dist[i] = 0; q.push(i); } while (!q.empty()) { int source = q.front(); q.pop(); // cout << "Source: " << source << '\n'; if (dist[nodes[source].left] == INF) { q.push(nodes[source].left); dist[nodes[source].left] = 1 + dist[source]; } if (dist[nodes[source].right] == INF) { q.push(nodes[source].right); dist[nodes[source].right] = 1 + dist[source]; } } int smallest = INF; for (int i = C; i <= D; i++) { smallest = min(smallest, dist[i]); } if (smallest == INF) { return -1; } return smallest; }
#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...