| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1204059 | jasonic | Rainforest Jumps (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
int n;
int l[200005];
int r[200005];
struct Element{
int idx, val;
Element(): val(-1), idx(-1) {};
Element(int a, int b): val(a), idx(b) {};
bool operator<(const Element &b) const {
return val < b.val;
}
bool operator>(const Element &b) const {
return val > b.val;
}
};
struct SegTree{
int l, r;
int mn, mx;
Element maxEl;
SegTree *lt, *rt;
void comb() {
mn = min(lt->mn, rt->mn);
mx = max(lt->mx, rt->mx);
maxEl = max(lt->maxEl, rt->maxEl);
}
SegTree(): l(0), r(0), mn(0), mx(0), lt(nullptr), rt(nullptr) {};
SegTree(int bl, int br, vector<Element> &a) {
l = bl; r = br;
lt = rt = nullptr;
mx = -1;
mn = n;
if(l == r) {
maxEl = a[l];
} else {
int m = l + (r-l)/2;
lt = new SegTree(l, m, a);
rt = new SegTree(m+1, r, a);
comb();
}
}
void upd(int i) {
if(i < l || r < i) return;
if(i == l && l == r) {
mn = mx = i;
} else {
lt->upd(i);
rt->upd(i);
comb();
}
}
int qryMx(int ql, int qr) {
if(qr < l || r < ql) return -1;
if(ql <= l && r <= qr) return mx;
else return max(lt->qryMx(ql, qr), rt->qryMx(ql, qr));
}
int qryMn(int ql, int qr) {
if(qr < l || r < ql) return n;
if(ql <= l && r <= qr) return mn;
else return min(lt->qryMn(ql, qr), rt->qryMn(ql, qr));
}
Element starting(int ql, int qr) {
if(qr < l || r < ql) return Element();
if(ql <= l && r <= qr) return maxEl;
else return max(lt->starting(ql, qr), rt->starting(ql, qr));
}
};
SegTree segtree;
unordered_map<int, vector<int>> adjList;
void connect(int x, int y) {
adjList[x].push_back(y);
}
void init(int N, int h[]) {
n = N;
set<int> process_idx;
vector<Element> a;
for(int i = 0; i < n; i++) {
a.push_back(Element(h[i], i));
}
segtree = SegTree(0, n-1, a);
sort(a.begin(), a.end(), greater());
for(int i = 0; i < n; i++) {
l[a[i].idx] = segtree.qryMx(0, max(a[i].idx, 0));
r[a[i].idx] = segtree.qryMn(min(a[i].idx, n-1), n-1);
segtree.upd(a[i].idx);
int x = a[i].idx;
int y = l[a[i].idx];
int z = r[a[i].idx];
if(y>=0) connect(x, y);
if(z<=n-1) connect(x, z);
}
}
int minimum_jumps(int a, int b, int c, int d) {
vector<int> dist(n, -1);
queue<int> bfs;
for(int i = a; i <= b; i++) {
dist[i] = 0;
bfs.push(i);
}
while(!bfs.empty()) {
int curr = bfs.front(); bfs.pop();
if(c <= curr && curr <= d) return dist[curr];
for(auto i : adjList[curr]) {
if(dist[i] != -1) continue;
dist[i] = dist[curr] + 1;
bfs.push(i);
}
}
return -1;
}