Submission #1201239

#TimeUsernameProblemLanguageResultExecution timeMemory
1201239dostsRainforest Jumps (APIO21_jumps)C++20
0 / 100
4098 ms25516 KiB
#include "jumps.h" #include <bits/stdc++.h> //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() using namespace std; struct ST { vector<pii> t; ST(){}; ST(int nn) { t.assign(4*nn+1,{0,0}); } void update(int node,int l,int r,int p,pii v) { if (l == r) { t[node] = v; return; } int m = (l+r) >> 1; if (p <= m) update(2*node,l,m,p,v); else update(2*node+1,m+1,r,p,v); t[node] = max(t[2*node],t[2*node+1]); } pii query(int node,int l,int r,int L,int R) { if (l > R || r < L) return {0,0}; if (l >= L && r <= R) return t[node]; int m = (l+r) >> 1; return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R)); } }st; int up[200005][20]; int n; vector<int> hh; void init(int N, std::vector<int> H) { hh = H; n = N; st = ST(n); for (int i=1;i<=N;i++) st.update(1,1,N,i,{H[i-1],i}); stack<int> stk; for (int j = 0;j<20;j++) up[n+1][j] = n+1; for (int i = N;i>=1;i--) { while (!stk.empty() && H[stk.top()-1] < H[i-1]) stk.pop(); if (stk.empty()) up[i][0] = n+1; else up[i][0] = stk.top(); stk.push(i); } for (int i=1;i<20;i++) { for (int j = 1;j<=N;j++) up[j][i] = up[up[j][i-1]][i-1]; } } int minimum_jumps(int A, int B, int C, int D) { A++,B++,C++,D++; assert(A<=B && B<C && C<=D); if (up[B][0] > D) return -1; if (B == C-1) return 1; pii p1 = st.query(1,1,n,A,B); pii p2 = st.query(1,1,n,C,D); pii p3 = st.query(1,1,n,B+1,C-1); if (p3.ff > p2.ff) return -1; int select = 0; for (int i = B;i>=A;i--) if (up[i][0] >= C && up[i][0] <= D) return 1; for (int i = B;i>=A;i--) { if (up[i][0] > B && up[i][0] <= D) select = i; } int p = select; int steps = 0; for (int i = 19;i>=0;i--) { if (up[p][i] < C) { steps+=(1<<i); p = up[p][i]; } } return steps+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...