Submission #981564

#TimeUsernameProblemLanguageResultExecution timeMemory
981564Ghulam_JunaidRainforest Jumps (APIO21_jumps)C++17
33 / 100
4051 ms570484 KiB
#include <bits/stdc++.h> #include "jumps.h" using namespace std; const int MXN = 2e5 + 10; const int T = 330; int n, pos[MXN], to_left[MXN], to_right[MXN], dp_left[MXN][T + 1], dp_right[MXN][T + 1]; vector<int> seg[4 * MXN], h; void build(int v = 1, int s = 0, int e = n){ if (e - s == 1){ seg[v] = {h[s]}; return; } int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1; build(lc, s, mid); build(rc, mid, e); seg[v] = seg[lc]; for (int x : seg[rc]) seg[v].push_back(x); sort(seg[v].begin(), seg[v].end()); } int get(int l, int r, int x, int v = 1, int s = 0, int e = n){ // int mx = -1; // for (int i = l; i < r; i ++) // if (h[i] < x) // mx = max(mx, h[i]); // return mx; if (e <= l || r <= s) return -1; if (l <= s && e <= r){ if (x > seg[v].back()) return seg[v].back(); if (x <= seg[v][0]) return -1; int lb = lower_bound(seg[v].begin(), seg[v].end(), x) - seg[v].begin(); return seg[v][lb - 1]; } int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1; return max(get(l, r, x, lc, s, mid), get(l, r, x, rc, mid, e)); } void init(int N, vector<int> H) { n = N; h = H; for (int i = 0; i < n; i ++) pos[h[i]] = i; build(); stack<int> S; for (int i = 0; i < n; i ++){ while(S.size() and h[S.top()] <= h[i]) S.pop(); if (S.size()) to_left[i] = S.top(); else to_left[i] = i; S.push(i); } while (S.size()) S.pop(); for (int i = n - 1; i >= 0; i --){ while (S.size() and h[S.top()] <= h[i]) S.pop(); if (S.size()) to_right[i] = S.top(); else to_right[i] = i; S.push(i); } // for (int i = 0; i < n; i ++){ // to_left[i] = to_right[i] = i; // for (int j = i + 1; j < n; j ++){ // if (h[j] > h[i]){ // to_right[i] = j; // break; // } // } // for (int j = i - 1; j >= 0; j --){ // if (h[j] > h[i]){ // to_left[i] = j; // break; // } // } // } for (int i = 0; i < n; i ++){ dp_left[i][1] = to_left[i]; dp_right[i][1] = to_right[i]; } for (int j = 2; j <= T; j ++){ for (int i = 0; i < n; i ++){ dp_left[i][j] = min(to_left[dp_left[i][j - 1]], to_left[dp_right[i][j - 1]]); dp_right[i][j] = max(to_right[dp_left[i][j - 1]], to_right[dp_right[i][j - 1]]); } } } int minimum_jumps(int A, int B, int C, int D) { B++, D++; int mx = get(C, D, n + 1); int l = A - 1, r = B - 1; if (get(r, C, n + 1) > mx) return -1; while (r - l > 1){ int mid = (l + r) / 2; if (get(mid, C, n + 1) > mx) l = mid; else r = mid; } int val = get(r, B, mx); if (val == -1) return -1; int st = pos[val]; if (get(st, C, n + 1) > mx) return -1; int ope = 0; if (C == D){ while (st < C){ if (h[dp_left[st][T]] < h[C] and h[dp_right[st][T]] < h[C]){ if (h[dp_left[st][T]] > h[dp_right[st][T]]) st = dp_left[st][T]; else st = dp_right[st][T]; ope += T; } else{ for (int i = 1; i < T; i ++){ if (h[dp_left[st][T - i]] < h[C] and h[dp_right[st][T - i]] < h[C]){ ope += T - i + 1; break; } } break; } } } else{ while (st < C){ ope++; int opt1 = to_left[st]; int opt2 = to_right[st]; if (opt2 >= C or h[opt2] > h[opt1] or h[opt1] > mx) st = opt2; else st = opt1; } } return ope; }
#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...