제출 #981589

#제출 시각아이디문제언어결과실행 시간메모리
981589Ghulam_Junaid밀림 점프 (APIO21_jumps)C++17
4 / 100
1025 ms570296 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[MXN][T + 1], dp_right[MXN][T + 1]; vector<int> seg[4 * MXN], h; bool subtask1 = 1; 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, subtask1 &= (h[i] == (i + 1)); 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[i][0] = i; dp_right[i][0] = i; for (int j = 1; j <= T; j ++){ dp[i][j] = (h[to_left[dp[i][j - 1]]] > h[to_right[dp[i][j - 1]]]) ? to_left[dp[i][j - 1]] : to_right[dp[i][j - 1]]; dp_right[i][j] = to_right[dp_right[i][j - 1]]; } } } int minimum_jumps(int A, int B, int C, int D) { if (subtask1) return C - B; 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 + 1 == D){ while (h[dp[st][T]] < h[C]){ st = dp[st][T]; ope += T; } for (int i = 1; i < T; i ++){ if (h[dp[st][T - i]] < h[C]){ st = dp[st][T - i]; ope += T - i; break; } } while (h[dp_right[st][T]] < h[C]){ st = dp_right[st][T]; ope += T; } for (int i = 1; i < T; i ++){ if (h[dp_right[st][T - i]] == h[C]){ ope += T - i; 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...