Submission #1035341

#TimeUsernameProblemLanguageResultExecution timeMemory
1035341AverageAmogusEnjoyerRainforest Jumps (APIO21_jumps)C++17
8 / 100
4069 ms5948 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]; int partree[nax]; 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); } for (int i=0;i<n;i++) { if (h[i] == n-1) { partree[i] = -1; continue; } assert(h[par[i][0]] != h[par[i][1]]); if (par[i][0] == n) { partree[i] = par[i][1]; } else if (par[i][1] == n) { partree[i] = par[i][0]; } else { partree[i] = (h[par[i][0]] > h[par[i][1]] ? par[i][0] : par[i][1]); } } } 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...