#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define show4(x,y,z, a) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << " " << #a << " is " << a << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef __int128 ull;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
ll n, h[200005], a, b, c, d;
ll twokr[200005][25],twokl[200005][25], hi[200005][25];
void init(int N, std::vector<int> H)
{
n = N;
h[0] = h[n+1] = LLONG_MAX;
twokl[0][0] = twokl[n+1][0] = 0, hi[0][0] = hi[n+1][0] = twokr[0][0] = twokr[n+1][0] = n+1;
for (ll i=1;i <=n; ++i) h[i] = H[i-1];
deque<ll> mono; // monotonically decreasing queue
for (ll i=1; i<=n; ++i)
{
if (mono.size() && h[mono.back()] <= h[i]) mono.pop_back();
twokl[i][0] = (mono.size()?mono.back(): i);
//show2(i, twokl[i][0]);
mono.pb(i);
}
mono.clear();
for (ll i=n ;i>=1; --i)
{
if (mono.size() && h[mono.back()] <= h[i]) mono.pop_back();
twokr[i][0] = (mono.size()?mono.back(): i);
//show2(i, twokr[i][0]);
hi[i][0] = ((h[twokl[i][0]]>h[twokr[i][0]])?twokl[i][0]:twokr[i][0]);
mono.pb(i);
}
// binary jumping
for (ll i=1; i<=18; ++i)
{
for (ll j=0; j<=n+1; ++j)
{
twokl[j][i] = twokl[twokl[j][i-1]][i-1];
twokr[j][i] = twokr[twokr[j][i-1]][i-1];
hi[j][i] = hi[hi[j][i-1]][i-1];
}
}
}
ll query(ll l, ll r)
{
//show2(l, r);
for (ll k=18; k>=0; --k)
{
if (twokr[l][k] > r) continue;
l = twokr[l][k];
}
return l;
}
int minimum_jumps(int A, int B, int C, int D)
{
a = A+1, b = B+1, c = C + 1, d = D+1;
// start with c
// c is either optmimal (low h) or need to be pass through (high h)
if (b+1 == c) // already adjacent, no need to 'swing' around
{
if (twokr[b][0] <= d) return 1;
return -1;
}
ll b4 = query(b+1, c-1);
if (h[b] > h[b4]) // ready to jump
{
if (twokr[b][0] <= d) return 1;
return -1;
}
ll st = b;
// go up as much as possible for free
for (ll i=18; i>=0; --i)
{
if (twokl[st][i] < a || h[twokl[st][i]] >= h[b4]) continue;
st = twokl[st][i];
}
// if already ready to jump
if (twokl[st][0] >= a && twokr[twokl[st][0]][0] <= d) return 1;
ll ans = 0;
if (twokl[st][0] < a)
{
//show(st);
//for (ll i=1; i<18; ++i) show(hi[4][i]);
// choose to jump to highest one until just before it reach b4
for (ll i=18; i>=0; --i)
{
//show(hi[st][i]);
if (h[hi[st][i]] >= h[b4]) continue;
st = hi[st][i];
//show(st);
ans += (1LL << i);
}
//show2(ans, st);
if (st == b4) // just nice at b4
{
if (twokr[st][0] <= d) return ans + 1;
return -1;
}
// take care of edges case
if (twokr[st][0] >= c && twokr[st][0] <= d) return ans + 1;
if (0 < twokl[st][0] && c <= twokr[twokl[st][0]][0] && twokr[twokl[st][0]][0] <= d) return ans + 2;
}
// last jump
for (ll j=18; j>=0; --j)
{
if (twokr[st][j] >= c) continue;
ans += (1LL<< j);
st = twokr[st][j];
}
if (twokr[st][0] >= c && twokr[st][0] <= d) return ans + 1;
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
160 ms |
97684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
160 ms |
97684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
