Submission #570380

#TimeUsernameProblemLanguageResultExecution timeMemory
570380grtRainforest Jumps (APIO21_jumps)C++17
33 / 100
4067 ms5312 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]; void init(int N, vi H) { n = N; for(int i = 0; i < n; ++i) { h[i + 1] = H[i]; } h[0] = INF, 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); } } int minimum_jumps(int a, int b, int c, int d) { a++, b++, c++, d++; int res = INF; 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; } //for(int x = a; x <= b; ++x) { int x = p; int ans = 0; //int xp = x; while(x < c) { if(h[lft[x]] <= H && h[rght[x]] <= H) { if(rght[x] >= c && rght[x] <= d) { ans++; break; } if(h[lft[x]] > h[rght[x]]) x = lft[x]; else x = rght[x]; } else if(h[lft[x]] <= H) { x = lft[x]; } else if(h[rght[x]] <= H) { x = rght[x]; } else { ans = INF; break; } ans++; } //x = xp; res = min(res, ans); //} return (res == INF ? -1 : res); } //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...