Submission #1035328

#TimeUsernameProblemLanguageResultExecution timeMemory
1035328AverageAmogusEnjoyerRainforest Jumps (APIO21_jumps)C++17
8 / 100
4078 ms5328 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; } template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; } mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); int rng() { return abs((int)mrand()); } // Current challenge: finish CSES problemset!! constexpr int nax = 200200; int h[nax]; int par[nax][2]; void init(int n, vector<int> H) { for (int i=0;i<n;i++) { h[i] = H[i]-1; par[i][0] = par[i][1] = n; } h[n] = n; vector<int> stk; for (int i=0;i<n;i++) { while(!stk.empty() && h[stk.back()] < h[i]) { stk.pop_back(); } if (!stk.empty()) par[i][0] = stk.back(); stk.push_back(i); } stk.clear(); for (int i=n-1;i>=0;i--) { while(!stk.empty() && h[stk.back()] < h[i]) { stk.pop_back(); } if (!stk.empty()) par[i][1] = stk.back(); stk.push_back(i); } } int jump(int a,int b) { int x = a; int ans = 0; assert(a!=b); while(true) { if (min(h[par[x][0]],h[par[x][1]]) > h[b]) { return nax; } if (par[x][0] == b) { x = par[x][0]; ans++; return ans; } if (par[x][1] == b) { x = par[x][1]; ans++; return ans; } if (h[par[x][0]] > h[b]) { x = par[x][1]; ans++; } else if (h[par[x][1]] > h[b]) { x = par[x][0]; ans++; } else { x = (h[par[x][0]] > h[par[x][1]] ? par[x][0] : par[x][1]); ans++; } } } int minimum_jumps(int a,int b,int c,int d) { int ans = nax; for (int A=a;A<=b;A++) { for (int C=c;C<=d;C++) { cmin(ans,jump(A,C)); } } return (ans == nax ? -1 : ans); }
#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...