제출 #922218

#제출 시각아이디문제언어결과실행 시간메모리
922218Arp밀림 점프 (APIO21_jumps)C++17
0 / 100
4067 ms5848 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int ml[N],mr[N]; int best[N]; int arr[N]; int MAXN; void init(int n,vector<int> a){ for(int i = 1;i<=n;i++){ ml[i] = 0; mr[i] = n + 1; arr[i] = a[i - 1]; } MAXN = n; arr[0] = arr[n + 1] = -1; stack<int> lg; for(int i = 1;i<=n;i++){ while(lg.size() > 0 && arr[lg.top()] < arr[i]) lg.pop(); if(lg.size() > 0){ ml[i] = lg.top(); } lg.push(i); } stack<int> rg; for(int i = n;i >= 1;i--){ while(rg.size() > 0 && arr[rg.top()] < arr[i]) rg.pop(); if(rg.size() > 0){ mr[i] = rg.top(); } rg.push(i); } for(int i = 1;i<=n;i++){ best[i] = (arr[ml[i]] > arr[mr[i]] ? ml[i] : mr[i]); } } int minimum_jumps(int a,int b,int c,int d){ a ++,b ++; c ++,d ++; int m2 = c; for(int i = c;i <= d;i ++){ if(arr[i] > arr[m2]) m2 = i; } int m1 = MAXN + 1; for(int i = a;i <= b;i++){ if(arr[i] > arr[m1] && arr[i] < arr[m2]) m1 = i; } if(m1 == MAXN + 1) return -1; int last = m1; int ans = 0; while(arr[last] < arr[best[last]] && arr[best[last]] < arr[m2]){ if(last >= c && last <= d) return ans; last = best[last]; assert(last < d); ans ++; } while(!(last >= c && last <= d)){ if(arr[last] > arr[m2] || last > d) return -1; last = mr[last]; ans ++; } return 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...