#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e16;
ll gcd(ll a , ll b){
if(a < b) swap(a , b);
if(b == 0) return a;
return gcd(b , a % b);
}
inline ll tav(ll n , ll k){
ll res = 1;
while(k > 0){
if(k & 1){
res *= n; res %= md;
}
n *= n; n %= md;
k >>= 1;
}
return res;
}
struct segtree {
int sz = 1;
vector<int> val;
void init(int n){
while(sz < n) sz <<= 1;
val.assign(sz << 1 , 0);
return;
}
void build(vector<int> &a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < sze(a)){
val[x] = a[lx];
}
return;
}
int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
build(a , ln , lx , m); build(a , rn , m , rx);
val[x] = max(val[ln] , val[rn]);
return;
}
void build(vector<int> &a){
build(a , 0 , 0 , sz);
return;
}
void set(int i , int k , int x , int lx , int rx){
if(rx - lx == 1){
val[x] = k;
return;
}
int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
if(i < m){
set(i , k , ln , lx , m);
} else {
set(i , k , rn , m , rx);
}
val[x] = max(val[ln] , val[rn]);
return;
}
void set(int i , int k){
set(i , k , 0 , 0 , sz);
return;
}
int cal(int l , int r , int x , int lx , int rx){
if(rx <= l || lx >= r) return 0;
if(rx <= r && lx >= l) return val[x];
int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
int a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
return max(a , b);
}
int cal(int l , int r){
return cal(l , r , 0 , 0 , sz);
}
void clear(){
sz = 1;
val.clear();
return;
}
};
int n;
segtree st;
vector<int> a , v;
int lf[maxn] , rt[maxn] , jal[maxn][20] , jar[maxn][20] , jan[maxn][20] , jax[maxn][20];
vector<pii> u;
int p[maxn];
void init(int N, vector<int> H){
memset(jal , -1 , sizeof(jal));
memset(jar , -1 , sizeof(jar));
memset(jan , -1 , sizeof(jan));
memset(jax , -1 , sizeof(jax));
a = H;
n = N;
for(int i = 0 ; i < n ; i++){
p[a[i]] = i;
}
for(int i = 0 ; i < n ; i++){
int h = -1;
while(!v.empty()){
int j = v.back();
if(a[j] > a[i]){
h = j;
break;
}
v.pop_back();
}
lf[i] = h;
v.push_back(i);
}
v.clear();
for(int i = n - 1 ; ~i ; i--){
int h = -1;
while(!v.empty()){
int j = v.back();
if(a[j] > a[i]){
h = j;
break;
}
v.pop_back();
}
rt[i] = h;
v.push_back(i);
}
for(int i = 0 ; i < n ; i++){
jal[i][0] = lf[i];
for(int j = 1 ; j < 20 ; j++){
if(jal[i][j - 1] == -1) break;
jal[i][j] = jal[jal[i][j - 1]][j - 1];
}
}
for(int i = n - 1 ; ~i ; i--){
jar[i][0] = rt[i];
for(int j = 1 ; j < 20 ; j++){
if(jar[i][j - 1] == -1) break;
jar[i][j] = jar[jar[i][j - 1]][j - 1];
}
}
for(int i = 0 ; i < n ; i++){
u.push_back({a[i] , i});
}
sort(all(u) , greater<pii>());
for(int e = 1 ; e < n ; e++){
int i = u[e].second;
if(lf[i] == -1){
jax[i][0] = rt[i];
} else if(rt[i] == -1){
jax[i][0] = lf[i];
} else {
if(a[lf[i]] > a[rt[i]]){
jax[i][0] = lf[i];
jan[i][0] = rt[i];
} else {
jax[i][0] = rt[i];
jan[i][0] = lf[i];
}
}
for(int j = 1 ; j < 20 ; j++){
if(jax[i][j - 1] == -1) break;
jax[i][j] = jax[jax[i][j - 1]][j - 1];
}
for(int j = 1 ; j < 20 ; j++){
if(jan[i][j - 1] == -1) break;
jan[i][j] = jan[jan[i][j - 1]][j - 1];
}
}
st.init(n);
st.build(a);
return;
}
int dis(int x , int y){
int res = 0;
for(int j = 19 ; ~j ; j--){
int h = jax[x][j];
if(h == -1) continue;
if(a[h] > a[y]) continue;
res += (1 << j);
x = h;
}
for(int j = 19 ; ~j ; j--){
int h = jan[x][j];
if(h == -1) continue;
if(a[h] > a[y]) continue;
res += (1 << j);
x = h;
}
return res;
}
int minimum_jumps(int l1, int r1, int l2, int r2){
r1++; r2++;
if(r1 == l1){
if(rt[r1 - 1] == -1 || rt[r1 - 1] >= r2) return -1;
return 1;
}
int d = st.cal(r1 , l2) , k = st.cal(l2 , r2);
if(d > k) return -1;
if(a[r1 - 1] > d){
if(a[r1 - 1] > k) return -1;
return 1;
}
int v = r1 - 1;
for(int j = 19 ; ~j ; j--){
int h = jal[v][j];
if(h < l1) continue;
if(a[h] > d) continue;
v = h;
}
int res = dis(v , p[d]) + 1;
if(lf[v] >= l1) return 1;
int o = v;
for(int j = 19 ; ~j ; j--){
int h = jal[o][j];
if(h == -1) continue;
if(a[h] > d) continue;
o = h;
}
o = lf[o];
if(o == -1) return res;
if(a[o] > k) return res;
res = min(res , dis(v , o) + 1);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
62928 KB |
Output is correct |
2 |
Correct |
27 ms |
62844 KB |
Output is correct |
3 |
Correct |
203 ms |
70696 KB |
Output is correct |
4 |
Correct |
1153 ms |
72164 KB |
Output is correct |
5 |
Correct |
925 ms |
67616 KB |
Output is correct |
6 |
Correct |
1093 ms |
72156 KB |
Output is correct |
7 |
Correct |
896 ms |
69924 KB |
Output is correct |
8 |
Correct |
1209 ms |
72164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
62864 KB |
Output is correct |
2 |
Correct |
24 ms |
62888 KB |
Output is correct |
3 |
Correct |
23 ms |
62908 KB |
Output is correct |
4 |
Correct |
23 ms |
62932 KB |
Output is correct |
5 |
Incorrect |
29 ms |
62944 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
62864 KB |
Output is correct |
2 |
Correct |
24 ms |
62888 KB |
Output is correct |
3 |
Correct |
23 ms |
62908 KB |
Output is correct |
4 |
Correct |
23 ms |
62932 KB |
Output is correct |
5 |
Incorrect |
29 ms |
62944 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
62920 KB |
Output is correct |
2 |
Correct |
24 ms |
62924 KB |
Output is correct |
3 |
Correct |
26 ms |
62820 KB |
Output is correct |
4 |
Correct |
27 ms |
62936 KB |
Output is correct |
5 |
Correct |
96 ms |
70164 KB |
Output is correct |
6 |
Correct |
138 ms |
71364 KB |
Output is correct |
7 |
Correct |
66 ms |
67180 KB |
Output is correct |
8 |
Correct |
126 ms |
71368 KB |
Output is correct |
9 |
Correct |
38 ms |
64140 KB |
Output is correct |
10 |
Correct |
128 ms |
71368 KB |
Output is correct |
11 |
Correct |
85 ms |
72168 KB |
Output is correct |
12 |
Incorrect |
102 ms |
71948 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
62936 KB |
Output is correct |
2 |
Correct |
24 ms |
62904 KB |
Output is correct |
3 |
Correct |
25 ms |
62824 KB |
Output is correct |
4 |
Correct |
285 ms |
66872 KB |
Output is correct |
5 |
Correct |
1029 ms |
71368 KB |
Output is correct |
6 |
Correct |
658 ms |
64580 KB |
Output is correct |
7 |
Correct |
810 ms |
71324 KB |
Output is correct |
8 |
Correct |
557 ms |
66208 KB |
Output is correct |
9 |
Correct |
890 ms |
71328 KB |
Output is correct |
10 |
Correct |
1022 ms |
72084 KB |
Output is correct |
11 |
Correct |
1066 ms |
72096 KB |
Output is correct |
12 |
Correct |
1175 ms |
72016 KB |
Output is correct |
13 |
Correct |
861 ms |
71348 KB |
Output is correct |
14 |
Correct |
1184 ms |
71772 KB |
Output is correct |
15 |
Correct |
900 ms |
72104 KB |
Output is correct |
16 |
Correct |
858 ms |
72164 KB |
Output is correct |
17 |
Correct |
26 ms |
62936 KB |
Output is correct |
18 |
Correct |
28 ms |
62868 KB |
Output is correct |
19 |
Correct |
29 ms |
62940 KB |
Output is correct |
20 |
Correct |
28 ms |
62928 KB |
Output is correct |
21 |
Correct |
32 ms |
62908 KB |
Output is correct |
22 |
Correct |
27 ms |
62928 KB |
Output is correct |
23 |
Correct |
27 ms |
62864 KB |
Output is correct |
24 |
Correct |
27 ms |
62940 KB |
Output is correct |
25 |
Correct |
25 ms |
62816 KB |
Output is correct |
26 |
Correct |
24 ms |
62932 KB |
Output is correct |
27 |
Correct |
34 ms |
63016 KB |
Output is correct |
28 |
Correct |
48 ms |
63076 KB |
Output is correct |
29 |
Correct |
49 ms |
63024 KB |
Output is correct |
30 |
Correct |
45 ms |
62948 KB |
Output is correct |
31 |
Correct |
43 ms |
63032 KB |
Output is correct |
32 |
Correct |
24 ms |
62892 KB |
Output is correct |
33 |
Correct |
80 ms |
67624 KB |
Output is correct |
34 |
Correct |
114 ms |
71440 KB |
Output is correct |
35 |
Correct |
84 ms |
72044 KB |
Output is correct |
36 |
Correct |
124 ms |
71348 KB |
Output is correct |
37 |
Correct |
159 ms |
71764 KB |
Output is correct |
38 |
Correct |
90 ms |
72248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
62936 KB |
Output is correct |
2 |
Correct |
24 ms |
62904 KB |
Output is correct |
3 |
Correct |
25 ms |
62824 KB |
Output is correct |
4 |
Correct |
285 ms |
66872 KB |
Output is correct |
5 |
Correct |
1029 ms |
71368 KB |
Output is correct |
6 |
Correct |
658 ms |
64580 KB |
Output is correct |
7 |
Correct |
810 ms |
71324 KB |
Output is correct |
8 |
Correct |
557 ms |
66208 KB |
Output is correct |
9 |
Correct |
890 ms |
71328 KB |
Output is correct |
10 |
Correct |
1022 ms |
72084 KB |
Output is correct |
11 |
Correct |
1066 ms |
72096 KB |
Output is correct |
12 |
Correct |
1175 ms |
72016 KB |
Output is correct |
13 |
Correct |
861 ms |
71348 KB |
Output is correct |
14 |
Correct |
1184 ms |
71772 KB |
Output is correct |
15 |
Correct |
900 ms |
72104 KB |
Output is correct |
16 |
Correct |
858 ms |
72164 KB |
Output is correct |
17 |
Correct |
26 ms |
62936 KB |
Output is correct |
18 |
Correct |
28 ms |
62868 KB |
Output is correct |
19 |
Correct |
29 ms |
62940 KB |
Output is correct |
20 |
Correct |
28 ms |
62928 KB |
Output is correct |
21 |
Correct |
32 ms |
62908 KB |
Output is correct |
22 |
Correct |
27 ms |
62928 KB |
Output is correct |
23 |
Correct |
27 ms |
62864 KB |
Output is correct |
24 |
Correct |
27 ms |
62940 KB |
Output is correct |
25 |
Correct |
25 ms |
62816 KB |
Output is correct |
26 |
Correct |
24 ms |
62932 KB |
Output is correct |
27 |
Correct |
34 ms |
63016 KB |
Output is correct |
28 |
Correct |
48 ms |
63076 KB |
Output is correct |
29 |
Correct |
49 ms |
63024 KB |
Output is correct |
30 |
Correct |
45 ms |
62948 KB |
Output is correct |
31 |
Correct |
43 ms |
63032 KB |
Output is correct |
32 |
Correct |
24 ms |
62892 KB |
Output is correct |
33 |
Correct |
80 ms |
67624 KB |
Output is correct |
34 |
Correct |
114 ms |
71440 KB |
Output is correct |
35 |
Correct |
84 ms |
72044 KB |
Output is correct |
36 |
Correct |
124 ms |
71348 KB |
Output is correct |
37 |
Correct |
159 ms |
71764 KB |
Output is correct |
38 |
Correct |
90 ms |
72248 KB |
Output is correct |
39 |
Correct |
27 ms |
62872 KB |
Output is correct |
40 |
Correct |
27 ms |
62928 KB |
Output is correct |
41 |
Correct |
29 ms |
62836 KB |
Output is correct |
42 |
Correct |
241 ms |
66836 KB |
Output is correct |
43 |
Correct |
1000 ms |
71324 KB |
Output is correct |
44 |
Correct |
483 ms |
64548 KB |
Output is correct |
45 |
Correct |
925 ms |
71372 KB |
Output is correct |
46 |
Correct |
526 ms |
66236 KB |
Output is correct |
47 |
Correct |
967 ms |
71300 KB |
Output is correct |
48 |
Correct |
1203 ms |
72112 KB |
Output is correct |
49 |
Correct |
988 ms |
72096 KB |
Output is correct |
50 |
Correct |
1112 ms |
72148 KB |
Output is correct |
51 |
Correct |
893 ms |
71352 KB |
Output is correct |
52 |
Correct |
1118 ms |
71712 KB |
Output is correct |
53 |
Correct |
937 ms |
72128 KB |
Output is correct |
54 |
Correct |
798 ms |
72120 KB |
Output is correct |
55 |
Correct |
24 ms |
62912 KB |
Output is correct |
56 |
Incorrect |
173 ms |
71316 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
62928 KB |
Output is correct |
2 |
Correct |
27 ms |
62844 KB |
Output is correct |
3 |
Correct |
203 ms |
70696 KB |
Output is correct |
4 |
Correct |
1153 ms |
72164 KB |
Output is correct |
5 |
Correct |
925 ms |
67616 KB |
Output is correct |
6 |
Correct |
1093 ms |
72156 KB |
Output is correct |
7 |
Correct |
896 ms |
69924 KB |
Output is correct |
8 |
Correct |
1209 ms |
72164 KB |
Output is correct |
9 |
Correct |
26 ms |
62864 KB |
Output is correct |
10 |
Correct |
24 ms |
62888 KB |
Output is correct |
11 |
Correct |
23 ms |
62908 KB |
Output is correct |
12 |
Correct |
23 ms |
62932 KB |
Output is correct |
13 |
Incorrect |
29 ms |
62944 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |