Submission #643971

#TimeUsernameProblemLanguageResultExecution timeMemory
643971colossal_pepeRainforest Jumps (APIO21_jumps)C++17
44 / 100
1182 ms47416 KiB
#include "jumps.h" #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; const int INF = 1e9; int n, k; vector<int> h, idx; vector<vector<int>> st_max, st_u, st_r; int rangeMax(int l, int r); int getStart(int a, int b, int t); int getMaxEndHeight(int c, int d); int goRight(int s, int c); void init(int N, vector<int> H) { n = N; h = H; k = __lg(n) + 1; idx.resize(n); st_max.resize(k, vector<int>(n)); for (int i = 0; i < n; i++) { h[i]--; idx[h[i]] = i; st_max[0][i] = h[i]; } st_u.resize(k, vector<int>(n)); stack<int> s; for (int i = 0; i < n; i++) { while (not s.empty() and s.top() <= h[i]) s.pop(); st_u[0][i] = s.empty() ? h[i] : s.top(); s.push(h[i]); } while (not s.empty()) s.pop(); st_r.resize(k, vector<int>(n)); for (int i = n - 1; i >= 0; i--) { while (not s.empty() and s.top() <= h[i]) s.pop(); st_u[0][i] = max(st_u[0][i], s.empty() ? h[i] : s.top()); st_r[0][i] = s.empty() ? h[i] : s.top(); s.push(h[i]); } for (int i = 1; i < k; i++) { for (int j = 0; j < n; j++) { if (j + (1 << i) - 1 < n) { st_max[i][j] = max(st_max[i - 1][j], st_max[i - 1][j + (1 << (i - 1))]); } st_u[i][j] = st_u[i - 1][idx[st_u[i - 1][j]]]; st_r[i][j] = st_r[i - 1][idx[st_r[i - 1][j]]]; } } } int minimum_jumps(int a, int b, int c, int d) { int e = idx[rangeMax(c, d)]; int s = getStart(a, b, e); if (s == -1) return -1; int ans = 0; for (int bit = k - 1; bit >= 0; bit--) { if (st_u[bit][s] < h[e]) { ans += (1 << bit); s = idx[st_u[bit][s]]; } } for (int bit = k - 1; bit >= 0; bit--) { if (st_r[bit][s] < h[e]) { ans += (1 << bit); s = idx[st_r[bit][s]]; } } return ans + 1; } int rangeMax(int l, int r) { if (l > r) return -1; int m = __lg(r - l + 1); return max(st_max[m][l], st_max[m][r - (1 << m) + 1]); } int getStart(int a, int b, int e) { int l = a, r = e; while (r - l) { int m = (l + r) / 2; if (rangeMax(m, e) > h[e]) l = m + 1; else r = m; } if (l > b) return -1; return idx[rangeMax(l, b)]; }
#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...