#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 262144;
ll N; vector<int> H;
const ll INF = 1e18;
const ll E = 17;
int mx[Nm][E+1]; //first,log2(len)
ll l2(ll x) {
return (31-__builtin_clz(x));
}
void mwipe() { //wipes memory
for (ll i=0;i<Nm;i++) {
for (ll j=0;j<=E;j++) {
mx[i][j]=-INF;
}
}
}
int gm(ll a, ll b) {
ll D = b-a+1; ll lD = l2(D); ll lDe = (1LL<<lD);
return max(mx[a][lD],mx[b-lDe+1][lD]);
}
ll lpt[Nm]; ll rpt[Nm]; bool el[Nm];
ll bjr[Nm][E+1]; //binary jump, go right
ll bjt[Nm][E+1]; //total binary jump
pii bst(ll x0, ll T) { //find max height <=T that is reachable: return {position, #(steps)}
ll x = x0;
ll e = E;
ll d = 0;
while (e>=0) {
if (bjt[x][e]<=T) {
x=bjt[x][e]; d+=(1LL<<e);
}
e--;
}
return {x,d};
}
ll bsr(ll x0, ll T) { //find height >= T
ll x = x0;
ll e = E;
ll d = 0;
while (e>=0) {
if (bjr[x][e]<=T) {
x=bjr[x][e]; d+=(1LL<<e);
}
e--;
}
return d;
}
void init(int N1, vector<int> H1) {
mwipe();
N=N1; H=H1;
for (ll i=0;i<N;i++) {
mx[i][0]=H[i];
}
for (ll e=1;e<=E;e++) {
for (ll x=0;x<=(Nm-(1LL<<E));x++) {
mx[x][e]=max(mx[x][e-1],mx[x+(1LL<<(e-1))][e-1]);
}
}
map<ll,ll> al;
al[INF]=INF;
for (ll i=0;i<N;i++) {
auto A = al.upper_bound(H[i]);
lpt[i]=(*A).second;
al[H[i]]=i;
A = al.find(H[i]);
while (A != al.begin()) {
auto B = prev(A);
if ((*B).second<(*A).second) {
al.erase(B);
} else {
break;
}
}
}
map<ll,ll> ar;
ar[INF]=INF;
for (ll i=(N-1);i>=0;i--) {
auto A = ar.upper_bound(H[i]);
rpt[i]=(*A).second;
ar[H[i]]=i;
A = ar.find(H[i]);
while (A != ar.begin()) {
auto B = prev(A);
if ((*B).second>(*A).second) {
ar.erase(B);
} else {
break;
}
}
}
for (ll i=0;i<N;i++) {
if (lpt[i]==INF || rpt[i]==INF) {
el[i]=0;
}
if (lpt[i]!=INF && rpt[i]!=INF) {
if (H[lpt[i]]<H[rpt[i]]) {
lpt[i]=INF; el[i]=0;
} else {
el[i]=1;
}
}
if (el[i]) {
bjt[i][0]=lpt[i];
bjr[i][0]=rpt[i];
} else {
bjt[i][0]=rpt[i];
bjr[i][0]=rpt[i];
}
}
for (ll e=1;e<=E;e++) {
for (ll i=0;i<N;i++) {
if (bjt[i][e-1]==INF) {
bjt[i][e]=INF;
} else {
bjt[i][e]=bjt[bjt[i][e-1]][e-1];
}
if (bjr[i][e-1]==INF) {
bjr[i][e]=INF;
} else {
bjr[i][e]=bjr[bjr[i][e-1]][e-1];
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
assert(A==B); assert(C==D);
if (gm(A,C-1)>H[C]) {
return -1;
}
pii p1 = bst(A,H[C]);
return (p1.second+bsr(p1.first,H[C]));
}
/*int main() {
init(7,{3,2,1,6,4,5,7});
cout << minimum_jumps(4,4,6,6) <<"\n";
//cout << minimum_jumps(1,3,5,6) <<"\n";
//cout << minimum_jumps(0,1,2,2) <<"\n";
}*/
Compilation message
jumps.cpp: In function 'void mwipe()':
jumps.cpp:16:13: warning: overflow in conversion from 'long long int' to 'int' changes value from '-1000000000000000000' to '1486618624' [-Woverflow]
16 | mx[i][j]=-INF;
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
18776 KB |
Output is correct |
2 |
Correct |
14 ms |
18688 KB |
Output is correct |
3 |
Runtime error |
188 ms |
157040 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
27 ms |
37976 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
27 ms |
37976 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
27 ms |
37976 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
18776 KB |
Output is correct |
2 |
Correct |
12 ms |
18792 KB |
Output is correct |
3 |
Correct |
14 ms |
18776 KB |
Output is correct |
4 |
Incorrect |
189 ms |
47268 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
18776 KB |
Output is correct |
2 |
Correct |
12 ms |
18792 KB |
Output is correct |
3 |
Correct |
14 ms |
18776 KB |
Output is correct |
4 |
Incorrect |
189 ms |
47268 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
18776 KB |
Output is correct |
2 |
Correct |
14 ms |
18688 KB |
Output is correct |
3 |
Runtime error |
188 ms |
157040 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |