제출 #466635

#제출 시각아이디문제언어결과실행 시간메모리
466635rainboy밀림 점프 (APIO21_jumps)C++17
100 / 100
1336 ms22184 KiB
#include "jumps.h" #include <vector> using namespace std; const int N = 200000; typedef vector<int> vi; int max(int a, int b) { return a > b ? a : b; } int aa[N], qu[N]; int ddp[N], pp[N], pp_[N]; int ddq[N], qq[N], qq_[N]; int ddl[N], ll[N], ll_[N]; int ddr[N], rr[N], rr_[N]; int n; void dfs(int *dd, int *pp, int *pp_, int i) { if (dd[i]) return; if (pp[i] == -1) dd[i] = 1, pp_[i] = -1; else { int p, p_; dfs(dd, pp, pp_, pp[i]); p = pp[i], p_ = pp_[p]; dd[i] = dd[p] + 1, pp_[i] = dd[p] - dd[pp_[p]] != dd[p_] - dd[pp_[p_]] ? p : pp_[p_]; } } void init(int n_, vi aa_) { int i, cnt; n = n_; for (i = 0; i < n; i++) aa[i] = aa_[i]; cnt = 0; for (i = 0; i < n; i++) { while (cnt && aa[qu[cnt - 1]] < aa[i]) cnt--; ll[i] = cnt == 0 ? -1 : qu[cnt - 1]; qu[cnt++] = i; } cnt = 0; for (i = n - 1; i >= 0; i--) { while (cnt && aa[qu[cnt - 1]] < aa[i]) cnt--; rr[i] = cnt == 0 ? -1 : qu[cnt - 1]; qu[cnt++] = i; } for (i = 0; i < n; i++) { pp[i] = ll[i] == -1 || rr[i] == -1 ? (ll[i] == -1 ? rr[i] : ll[i]) : (aa[ll[i]] < aa[rr[i]] ? ll[i] : rr[i]); qq[i] = ll[i] == -1 || rr[i] == -1 ? (ll[i] == -1 ? rr[i] : ll[i]) : (aa[ll[i]] > aa[rr[i]] ? ll[i] : rr[i]); } for (i = 0; i < n; i++) { dfs(ddp, pp, pp_, i); dfs(ddq, qq, qq_, i); dfs(ddl, ll, ll_, i); dfs(ddr, rr, rr_, i); } } int minimum_jumps(int w, int x, int y, int z) { int i, j, k, a; j = y; while (1) if (rr_[j] != -1 && rr_[j] <= z) j = rr_[j]; else if (rr[j] != -1 && rr[j] <= z) j = rr[j]; else break; i = x; while (1) if (ll_[i] != -1 && ll_[i] >= w && aa[ll_[i]] < aa[j]) i = ll_[i]; else if (ll[i] != -1 && ll[i] >= w && aa[ll[i]] < aa[j]) i = ll[i]; else break; if (aa[i] > aa[j]) return -1; a = -1; if (x + 1 < y) { k = x + 1; while (1) if (rr_[k] != -1 && rr_[k] < y) k = rr_[k]; else if (rr[k] != -1 && rr[k] < y) k = rr[k]; else break; a = aa[k]; } if (a > aa[j]) return -1; k = 0; while (1) if (qq_[i] != -1 && aa[qq_[i]] <= a) k += ddq[i] - ddq[qq_[i]], i = qq_[i]; else if (qq[i] != -1 && aa[qq[i]] <= a) k++, i = qq[i]; else break; if (qq[i] != -1 && aa[qq[i]] <= aa[j]) return k + (rr[i] != -1 && rr[i] >= y ? 1 : 2); while (1) if (pp_[i] != -1 && aa[pp_[i]] <= a) k += ddp[i] - ddp[pp_[i]], i = pp_[i]; else if (pp[i] != -1 && aa[pp[i]] <= a) k++, i = pp[i]; else break; if (pp[i] != -1 && aa[pp[i]] <= aa[j]) return k + (rr[i] != -1 && rr[i] >= y ? 1 : 2); return -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...