Submission #1203430

#TimeUsernameProblemLanguageResultExecution timeMemory
1203430emad234Rainforest Jumps (APIO21_jumps)C++17
0 / 100
1435 ms45468 KiB
#include "jumps.h" #include <bits/stdc++.h> #define ll long long #define F first #define S second #define pii pair<int, int> const int mxN = 4e5 + 5; using namespace std; int st0[mxN][32],st1[mxN][32]; pii seg[1000005]; int NN; pii query(int l,int r,int ind,int s,int e){ if(l > e || r < s) return {0,0}; if(l >= s && r <= e) return seg[ind]; int md = (l + r) / 2; return max(query(l,md,ind * 2,s,e),query(md + 1,r,ind * 2 + 1,s,e)); } vector<int>h; int find(int l,int r,int val,bool sd){ // if(l == 19) cout<<l<<' '<<r<<'\n'; if(l > r || query(1,NN,1,l,r).F < val) return -1; if(l == r) return query(1,NN,1,l,r).S; int md = (l + r) / 2; auto a = query(1,NN,1,l,md), b = query(1,NN,1,md + 1,r); if (sd){ if(a.F > val) return find(l,md,val,sd); return find(md + 1,r,val,sd); }else{ if(b.F > val) return find(md + 1,r,val,sd); return find(l,md,val,sd); } } int solve(int x,int val,int C,int D){ int ans = 0; for(int i = 20;i >= 0;i--){ if(h[st1[x][i]] < val && !(st1[st1[x][i]][0] >= C && st1[st1[x][i]][0] <= D) && !(st0[st1[x][i]][0] >= C && st0[st1[x][i]][0] <= D)){ x = st1[x][i]; ans += (1 << i); // cout<<i<<' '<<x<<' '<<ans<<'\n'; } } // cout<<st1[x][0]<<' '<<C<<' '<<D<<'\n'; if((st1[x][0] >= C && st1[x][0] <= D) || (st0[x][0] >= C && st0[x][0] <= D)) return ans + 1; if(h[st1[x][0]] < val) { ans++; x = st1[x][0]; } for(int i = 20;i >= 0;i--){ if(h[st0[x][i]] < val && !(st0[x][i] >= C && st0[x][i] <= D)){ x = st0[x][i]; ans += (1 << i); } } ans++; return {ans}; } void init(int N, vector<int> H) { NN = exp2(ceil(log2(N))); for(int i = 0;i < N;i++){ seg[i + NN] = {H[i],i}; } h = H; for(int i = NN - 1;i;i--) seg[i] = max(seg[i * 2],seg[i * 2 + 1]); for(int i = 0;i < N;i++){ int a = find(1,i,H[i],0),b = find(i + 2,N,H[i],1); // cout<<i<<' '<<a<<' '<<b<<'\n'; if(h[a] < h[b]) swap(a,b); if(a == -1) a = i; if(b == -1) b = i; st1[i][0] = a; st0[i][0] = b; } for(int pw = 1;pw <= 20;pw++){ for(int i = 0;i < N;i++){ st1[i][pw] = st1[st1[i][pw - 1]][pw - 1]; st0[i][pw] = st0[st0[i][pw - 1]][pw - 1]; // cout<<st1[i][pw]<<' '; } // cout<<'\n'; } } int minimum_jumps(int A, int B, int C, int D) { A++; B++; C++; D++; // if(A != B || C != D) assert(1); int mxA = query(1,NN,1,A,B).F,mxidA = query(1,NN,1,A,B).S,mxC = query(1,NN,1,C,D).F,mxidC = query(1,NN,1,C,D).S; // // cout<<mxA<<' '<<mxidA<<' '<<mxC<<' '<<mxidC<<'\n'; if(query(1,NN,1,B,C - 1).F > mxC) return -1; int x; if(mxC > mxA) x = mxidA; else{ x = find(A,B,mxC,0); x = query(1,NN,1,x + 2,B).S; } return solve(x,mxC,C - 1,D - 1); } // 20 3 // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 // 0 0 6 6 // 3 4 5 6 // 2 2 5 6
#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...