제출 #643758

#제출 시각아이디문제언어결과실행 시간메모리
643758colossal_pepe밀림 점프 (APIO21_jumps)C++17
4 / 100
1318 ms47248 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 getEnd(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 = getEnd(c, d); int s = getStart(a, b, h[e]); if (s == -1) return -1; int jumps = 0; int ans = jumps + goRight(s, c); for (int bit = k - 1; bit >= 0; bit--) { if (st_u[bit][s] < h[e]) { jumps += (1 << bit); s = idx[st_u[bit][s]]; ans = min(ans, jumps + goRight(s, c)); } } return ans; } int rangeMax(int l, int r) { 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 t) { int l = a, r = b; while (r - l) { int m = (l + r) / 2; if (rangeMax(m, b) > t) l = m + 1; else r = m; } if (rangeMax(l, b) > t) return -1; return idx[rangeMax(l, b)]; } int getEnd(int c, int d) { return idx[rangeMax(c, d)]; } int goRight(int s, int c) { int jumps = 0; for (int bit = k - 1; bit >= 0; bit--) { if (st_r[bit][s] < h[c]) { jumps += (1 << bit); s = st_r[bit][s]; } } return jumps + 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...