#include<bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
const int INF = (int)1e9+71;
/* Segment Tree */
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
/* S op(S a, S b) {} -> Value combine function */
/* S e() {} -> Initial value */
int _n;
vector<S> d;
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(vector<S>(n, e())) {}
explicit segtree(const vector<S>& v) : _n(int(v.size())) {
d.assign(4*_n, e());
build(v);
}
void build(vector<S> a, int v=1, int tl=0, int tr=-1){
if(tr == -1) tr = _n-1;
if(tl == tr){
d[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
d[v] = op(d[v*2], d[v*2+1]);
}
}
int get_first(int l, int r, int x, int v=1, int lv=0, int rv=-1) {
if(rv==-1) rv=_n-1;
// cout << l << " " << r << " " << x << " " << v << " " << lv << " " << rv << endl;
if(lv > r || rv < l) return -1;
if(l <= lv && rv <= r) {
if(d[v] <= x) return -1;
while(lv != rv) {
int mid = lv + (rv-lv)/2;
if(d[2*v] > x) {
v = 2*v;
rv = mid;
} else {
v = 2*v+1;
lv = mid+1;
}
}
return lv;
}
int mid = lv + (rv-lv)/2;
int rs = get_first(l, r, x, 2*v, lv, mid);
if(rs != -1) return rs;
return get_first(l ,r, x, 2*v+1, mid+1, rv);
}
int get_last(int l, int r, int x, int v=1, int lv=0, int rv=-1) {
if(rv==-1) rv=_n-1;
if(lv > r || rv < l) return -1;
if(l <= lv && rv <= r) {
if(d[v] <= x) return -1;
while(lv != rv) {
int mid = lv + (rv-lv)/2;
if(d[2*v+1] > x) {
v = 2*v+1;
lv = mid+1;
} else {
v = 2*v;
rv = mid;
}
}
return lv;
}
int mid = lv + (rv-lv)/2;
int rs = get_last(l ,r, x, 2*v+1, mid+1, rv);
if(rs != -1) return rs;
return get_last(l, r, x, 2*v, lv, mid);
}
};
/* End: Segment Tree */
vector<int> Trees;
vector<vector<ll>> edges;
int n;
int op(int a, int b){ return max(a,b); }
int e() { return INF; }
void init(int N, vector<int> H) {
n = N; Trees = H;
segtree<int, op, e> st(H);
edges.assign(n, {});
for(int i=0;i<n;i++){
if(i != 0){
// find to the left
int res = st.get_last(0, i-1, H[i]);
if(res != -1) edges[i].pb(res);
}
if(i != n-1){
// cout << i << " " << __LINE__ << endl;
int res = st.get_first(i+1, n-1, H[i]);
if(res != -1) edges[i].pb(res);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
assert(A==B && C==D);
vector<ll> distance;
vector<bool> processed(n);
distance.assign(n, INF);
distance[A] = 0;
priority_queue<ii> q;
q.push({0,A});
while (!q.empty()) {
int a = q.top().second; q.pop();
if (processed[a]) continue;
processed[a] = true;
for (auto b : edges[a]) {
if (distance[a]+1 < distance[b]) {
distance[b] = distance[a]+1;
q.push({-distance[b],b});
}
}
}
return (distance[C]==INF?-1:distance[C]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Execution timed out |
4046 ms |
16796 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
328 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
328 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
456 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct |
| 4 |
Execution timed out |
4040 ms |
10340 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct |
| 4 |
Execution timed out |
4040 ms |
10340 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Execution timed out |
4046 ms |
16796 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
