제출 #424053

#제출 시각아이디문제언어결과실행 시간메모리
424053SorahISA밀림 점프 (APIO21_jumps)C++17
48 / 100
1690 ms44964 KiB
#include "jumps.h" #pragma GCC optimize("Ofast", "unroll-loops") #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; template<typename T> using Prior = std::priority_queue<T>; template<typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>; #define X first #define Y second #define eb emplace_back #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); inline int getRand(int L, int R) { if (L > R) swap(L, R); return (int)(rng() % (uint64_t)(R - L + 1) + L); } const int INF = 1E9; const int maxn = 1 << 18; const int lgmx = 18; // const int maxn = 1 << 4; // const int lgmx = 4; int N, sparse[lgmx][maxn], inv[maxn]; pii jump[lgmx][maxn]; /// (jump lo_edge, jump hi_edge) vector<int> H; inline int chmin(int &x, int y) {return x <= y ? 0 : x = y, 1;} inline int QueryMax(int L, int R) { int lay = __lg(R - L + 1); return max(sparse[lay][L], sparse[lay][R - (1<<lay) + 1]); } void init(int _N, vector<int> _H) { N = _N + 2; H.eb(N + 1); for (auto x : _H) H.eb(x); H.eb(N + 2); for (int i = 0; i < N; ++i) sparse[0][i] = H[i], inv[H[i]] = i; for (int lay = 1; lay < lgmx; ++lay) { for (int i = 0; i < N-(1<<lay)+1; ++i) { sparse[lay][i] = max(sparse[lay-1][i], sparse[lay-1][i+(1<<lay-1)]); } } jump[0][0] = {0, N-1}, jump[0][N-1] = {N-1, N-1}; for (int i = 1, lo, mi, hi; i < N-1; ++i) { auto &jmp = jump[0][i]; lo = 0, hi = i; while (lo < hi) { mi = lo + hi + 1 >> 1; QueryMax(mi, i) > H[i] ? lo = mi : hi = mi - 1; } jmp.X = lo; lo = i, hi = N-1; while (lo < hi) { mi = lo + hi >> 1; QueryMax(i, mi) > H[i] ? hi = mi : lo = mi + 1; } jmp.Y = lo; if (H[jmp.X] > H[jmp.Y]) swap(jmp.X, jmp.Y); } for (int lay = 1; lay < lgmx; ++lay) { for (int i = 0; i < N; ++i) { auto anc = jump[lay-1][i]; jump[lay][i].X = jump[lay-1][anc.X].X; jump[lay][i].Y = jump[lay-1][anc.Y].Y; } } } int minimum_jumps(int A, int B, int C, int D) { ++A, ++B, ++C, ++D; int lo = A, hi = B, mi; while (lo < hi) { mi = lo + hi >> 1; if (QueryMax(mi, B) > H[C]) lo = mi + 1; else hi = mi; } A = B = inv[QueryMax(lo, B)]; // cout << "start at " << A - 1 << "\n"; int ans = 0; for (int i = lgmx-1; i >= 0; --i) { if (H[jump[i][A].Y] <= H[C]) A = jump[i][A].Y, ans += 1 << i; } for (int i = lgmx-1; i >= 0; --i) { if (H[jump[i][A].X] <= H[C]) A = jump[i][A].X, ans += 1 << i; } return A == C ? ans : -1; }

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:50:75: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |             sparse[lay][i] = max(sparse[lay-1][i], sparse[lay-1][i+(1<<lay-1)]);
      |                                                                        ~~~^~
jumps.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             mi = lo + hi + 1 >> 1;
      |                  ~~~~~~~~^~~
jumps.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |             mi = lo + hi >> 1;
      |                  ~~~^~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:90:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         mi = lo + hi >> 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...