| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 737492 | keisuke6 | Rainforest Jumps (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "jumps.h"
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> G(200100);
int n;
struct SEG{
private:
int n;
vector<int> node;
public:
SEG(int N){
n = 1;
while(n < N) n *= 2;
node.resize(2*n-1,0);
}
void update(int i, int x){
i += n-1;
node[i] = x;
while(i > 0){
i--;
i /= 2;
node[i] = min(node[2*i+1],node[2*i+2]);
}
return;
}
int query(int a, int b, int k = 0, int l = 0, int r = -1){
if(r < 0) r = n;
if(a > b) return 0;
if(b <= l || r <= a) return 0;
if(a <= l && r <= b) return node[k];
int vl = query(a,b,2*k+1,l,(l+r)/2);
int vr = query(a,b,2*k+2,(l+r)/2,r);
return max(vl,vr);
}
};
SEG seg;
void init(int N, std::vector<int> H) {
n = N;
SEG segg(n);
for(int i=0;i<N;i++) seg.update(i,H[i]);
for(int i=0;i<N;i++){
if(seg.query(0,i-1) > H[i]){
int ac = 0, wa = i-1;
while(wa-ac > 1){
int wj = (ac+wa)/2;
if(seg.query(wj,i-1) > H[i]) ac = wj;
else wa = wj;
}
G[i].push_back(ac);
}
if(seg.query(i+1,N)){
int ac = N, wa = i+1;
while(ac-wa > 1){
int wj = (ac+wa)/2;
if(seg.query(i+1,wj) > H[i]) ac = wj;
else wa = wj;
}
G[i].push_back(wa);
}
}
seg = segg;
return;
}
int minimum_jumps(int A, int B, int C, int D) {
vector<int> dist(n,1e9);
queue<int> q;
for(int i=A;i<=B;i++){
dist[i] = 0;
q.push(i);
}
while(!q.empty()){
int pos = q.front();
q.pop();
for(int x:G[pos]){
if(dist[x] != 1e9) continue;
dist[x] = dist[pos] + 1;
q.push(x);
}
}
int ans = 1e9;
for(int i=C;i<=D;i++) ans = min(ans,dist[i]);
return (ans == 1e9 ? -1 : ans);
}