제출 #570388

#제출 시각아이디문제언어결과실행 시간메모리
570388grt밀림 점프 (APIO21_jumps)C++17
56 / 100
4082 ms49724 KiB
#include <bits/stdc++.h> #define PB push_back #define ST first #define ND second //#pragma GCC optimize ("O3") //#pragma GCC target("tune=native") //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; //typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; using namespace std; using ll = long long; using pi = pair<int, int>; using vi = vector<int>; const int nax = 200 * 1000 + 10, INF = 1e9 + 10; int n; int h[nax]; int lft[nax], rght[nax]; int par[nax][19]; int par2[nax][19]; int mx[nax][19]; void init(int N, vi H) { n = N; for(int i = 0; i < n; ++i) { h[i + 1] = H[i]; } h[0] = INF + 1, h[n + 1] = INF; vi S = {0}; for(int i = 1; i <= n; ++i) { while(h[S.back()] < h[i]) S.pop_back(); lft[i] = S.back(); S.PB(i); } S = {n + 1}; for(int i = n; i >= 1; --i) { while(h[S.back()] < h[i]) S.pop_back(); rght[i] = S.back(); S.PB(i); } for(int i = 1; i <= n; ++i) { if(h[lft[i]] > h[rght[i]]) { par[i][0] = lft[i]; par2[i][0] = rght[i]; } else { par[i][0] = rght[i]; par2[i][0] = lft[i]; } mx[i][0] = max(lft[i], rght[i]); } par[n + 1][0] = 0; par2[n + 1][0] = 0; for(int j = 1; j < 19; ++j) { for(int i = 1; i <= n + 1; ++i) { par[i][j] = par[par[i][j - 1]][j - 1]; par2[i][j] = par2[par2[i][j - 1]][j - 1]; mx[i][j] = max(mx[i][j - 1], mx[par[i][j - 1]][j - 1]); } } } int minimum_jumps(int a, int b, int c, int d) { a++, b++, c++, d++; int H = -1; for(int i = c; i <= d; ++i) { H = max(H, h[i]); } int p = b; for(int i = b - 1; i >= a; --i) { if(h[i] > H) break; if(h[p] < h[i]) p = i; } int ans = 0; for(int i = 18; i >= 0; --i) { if(h[par[p][i]] <= H && mx[p][i] < c) { p = par[p][i]; ans += (1 << i); } } if(mx[p][0] >= c) { ans++; p = mx[p][0]; } else { for(int i = 18; i >= 0; --i) { if(h[par2[p][i]] <= H && par2[p][i] < c) { p = par2[p][i]; ans += (1 << i); } } p = par2[p][0]; ans++; } if(p < c || p > d) return -1; return ans; } //int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //init(7, {3, 2, 1, 6, 4, 5, 7}); //cout << minimum_jumps(4, 4, 6, 6) << "\n"; //cout << minimum_jumps(1, 3, 5, 6) << "\n"; //cout << minimum_jumps(0, 1, 2, 2) << "\n"; //}
#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...