/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 2e5+23, lg = 18;
int n, l[N], r[N], f[lg][N], f2[lg][N], spl[lg][N], spr[lg][N], h[N];
void init(int _n, vector<int> _h) {
n=_n; for(int i=1; i<=n; i++) h[i] = _h[i-1];
h[0] = 1e9+1, h[n+1] = 1e9+2;
for(int i=1; i<=n; i++) {
l[i] = i-1;
while(h[i] > h[l[i]]) l[i] = l[l[i]];
spl[0][i] = i;
for(int j=1; j<lg; j++) {
int x=spl[j-1][i], y=spl[j-1][max(0,i-(1<<(j-1)))];
spl[j][i] = (h[x]>h[y] ? x : y);
}
}
for(int i=0; i<lg; i++) f2[i][n+1] = f[i][n+1] = spr[i][n+1] = n+1;
for(int i=n; i>=1; i--) {
r[i] = i+1;
while(h[i] > h[r[i]]) r[i] = r[r[i]];
if(l[i]==0 || (r[i]<=n && h[r[i]] > h[l[i]])) f[0][i] = r[i], f2[0][i] = r[i];
else f[0][i] = l[i], f2[0][i] = r[i];
spr[0][i] = i;
for(int j=1; j<lg; j++) {
int x=spr[j-1][i], y=spr[j-1][min(n+1,i+(1<<(j-1)))];
spr[j][i] = (h[x]>h[y] ? x : y);
}
}
for(int i=1; i<lg; i++) {
for(int j=1; j<=n; j++) {
f[i][j] = f[i-1][f[i-1][j]];
f2[i][j] = f2[i-1][f2[i-1][j]];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
a++, b++, c++, d++;
int mxv=n+2, mxu=b, tmp=c, ans=0;
for(int i=lg-1; i>=0; i--) {
if(tmp+(1<<i)-1 <= d) mxv = (h[mxv]>h[spr[i][tmp]] ? mxv : spr[i][tmp]), tmp += (1<<i);
}
tmp = b;
for(int i=lg-1; i>=0; i--) {
if(spl[i][mxu] >= a && h[spl[i][mxu]] < h[mxv]) {
mxu = spl[i][tmp];
}
}
for(int i=lg-1; i>=0; i--) {
if(h[f[i][mxu]] < h[mxv] && f[i][mxu] < c && r[f[i][mxu]] < c) ans += (1<<i), mxu = f[i][mxu];
}
if(r[mxu] < c && f[0][mxu] < c && h[f[0][mxu]] < h[mxv]) {
ans ++; mxu = f[0][mxu];
}
for(int i=lg-1; i>=0; i--) {
if(f2[i][mxu] < c) mxu = f2[i][mxu], ans += (1<<i);
}
if(mxu >= c && mxu <= d) return ans;
int res = f2[0][mxu];
if(res>=c && res<=d) {
return ans+1;
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
57688 KB |
Output is correct |
2 |
Correct |
8 ms |
57688 KB |
Output is correct |
3 |
Correct |
134 ms |
59984 KB |
Output is correct |
4 |
Correct |
831 ms |
60612 KB |
Output is correct |
5 |
Correct |
722 ms |
59116 KB |
Output is correct |
6 |
Correct |
788 ms |
60620 KB |
Output is correct |
7 |
Correct |
632 ms |
59592 KB |
Output is correct |
8 |
Correct |
779 ms |
60596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
57688 KB |
Output is correct |
2 |
Correct |
8 ms |
57688 KB |
Output is correct |
3 |
Correct |
8 ms |
57688 KB |
Output is correct |
4 |
Correct |
8 ms |
57688 KB |
Output is correct |
5 |
Incorrect |
9 ms |
57940 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
57688 KB |
Output is correct |
2 |
Correct |
8 ms |
57688 KB |
Output is correct |
3 |
Correct |
8 ms |
57688 KB |
Output is correct |
4 |
Correct |
8 ms |
57688 KB |
Output is correct |
5 |
Incorrect |
9 ms |
57940 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
57688 KB |
Output is correct |
2 |
Correct |
8 ms |
57688 KB |
Output is correct |
3 |
Correct |
8 ms |
57688 KB |
Output is correct |
4 |
Correct |
8 ms |
57688 KB |
Output is correct |
5 |
Incorrect |
40 ms |
59944 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
57688 KB |
Output is correct |
2 |
Correct |
8 ms |
57796 KB |
Output is correct |
3 |
Correct |
9 ms |
57688 KB |
Output is correct |
4 |
Correct |
196 ms |
59108 KB |
Output is correct |
5 |
Correct |
645 ms |
60584 KB |
Output is correct |
6 |
Correct |
407 ms |
58200 KB |
Output is correct |
7 |
Correct |
644 ms |
60616 KB |
Output is correct |
8 |
Correct |
365 ms |
58828 KB |
Output is correct |
9 |
Correct |
651 ms |
60612 KB |
Output is correct |
10 |
Correct |
773 ms |
60496 KB |
Output is correct |
11 |
Correct |
821 ms |
60612 KB |
Output is correct |
12 |
Correct |
833 ms |
60588 KB |
Output is correct |
13 |
Correct |
699 ms |
60600 KB |
Output is correct |
14 |
Correct |
761 ms |
60696 KB |
Output is correct |
15 |
Correct |
672 ms |
60496 KB |
Output is correct |
16 |
Correct |
741 ms |
60616 KB |
Output is correct |
17 |
Correct |
8 ms |
57688 KB |
Output is correct |
18 |
Correct |
8 ms |
57688 KB |
Output is correct |
19 |
Correct |
9 ms |
57688 KB |
Output is correct |
20 |
Correct |
9 ms |
57864 KB |
Output is correct |
21 |
Correct |
10 ms |
57688 KB |
Output is correct |
22 |
Correct |
9 ms |
57688 KB |
Output is correct |
23 |
Correct |
8 ms |
57688 KB |
Output is correct |
24 |
Correct |
9 ms |
57688 KB |
Output is correct |
25 |
Correct |
8 ms |
57688 KB |
Output is correct |
26 |
Correct |
8 ms |
57688 KB |
Output is correct |
27 |
Correct |
18 ms |
57688 KB |
Output is correct |
28 |
Correct |
17 ms |
57688 KB |
Output is correct |
29 |
Correct |
17 ms |
57688 KB |
Output is correct |
30 |
Correct |
17 ms |
57688 KB |
Output is correct |
31 |
Correct |
21 ms |
57688 KB |
Output is correct |
32 |
Correct |
8 ms |
57688 KB |
Output is correct |
33 |
Correct |
31 ms |
59224 KB |
Output is correct |
34 |
Correct |
55 ms |
60616 KB |
Output is correct |
35 |
Correct |
61 ms |
60604 KB |
Output is correct |
36 |
Correct |
47 ms |
60712 KB |
Output is correct |
37 |
Correct |
51 ms |
60616 KB |
Output is correct |
38 |
Correct |
46 ms |
60624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
57688 KB |
Output is correct |
2 |
Correct |
8 ms |
57796 KB |
Output is correct |
3 |
Correct |
9 ms |
57688 KB |
Output is correct |
4 |
Correct |
196 ms |
59108 KB |
Output is correct |
5 |
Correct |
645 ms |
60584 KB |
Output is correct |
6 |
Correct |
407 ms |
58200 KB |
Output is correct |
7 |
Correct |
644 ms |
60616 KB |
Output is correct |
8 |
Correct |
365 ms |
58828 KB |
Output is correct |
9 |
Correct |
651 ms |
60612 KB |
Output is correct |
10 |
Correct |
773 ms |
60496 KB |
Output is correct |
11 |
Correct |
821 ms |
60612 KB |
Output is correct |
12 |
Correct |
833 ms |
60588 KB |
Output is correct |
13 |
Correct |
699 ms |
60600 KB |
Output is correct |
14 |
Correct |
761 ms |
60696 KB |
Output is correct |
15 |
Correct |
672 ms |
60496 KB |
Output is correct |
16 |
Correct |
741 ms |
60616 KB |
Output is correct |
17 |
Correct |
8 ms |
57688 KB |
Output is correct |
18 |
Correct |
8 ms |
57688 KB |
Output is correct |
19 |
Correct |
9 ms |
57688 KB |
Output is correct |
20 |
Correct |
9 ms |
57864 KB |
Output is correct |
21 |
Correct |
10 ms |
57688 KB |
Output is correct |
22 |
Correct |
9 ms |
57688 KB |
Output is correct |
23 |
Correct |
8 ms |
57688 KB |
Output is correct |
24 |
Correct |
9 ms |
57688 KB |
Output is correct |
25 |
Correct |
8 ms |
57688 KB |
Output is correct |
26 |
Correct |
8 ms |
57688 KB |
Output is correct |
27 |
Correct |
18 ms |
57688 KB |
Output is correct |
28 |
Correct |
17 ms |
57688 KB |
Output is correct |
29 |
Correct |
17 ms |
57688 KB |
Output is correct |
30 |
Correct |
17 ms |
57688 KB |
Output is correct |
31 |
Correct |
21 ms |
57688 KB |
Output is correct |
32 |
Correct |
8 ms |
57688 KB |
Output is correct |
33 |
Correct |
31 ms |
59224 KB |
Output is correct |
34 |
Correct |
55 ms |
60616 KB |
Output is correct |
35 |
Correct |
61 ms |
60604 KB |
Output is correct |
36 |
Correct |
47 ms |
60712 KB |
Output is correct |
37 |
Correct |
51 ms |
60616 KB |
Output is correct |
38 |
Correct |
46 ms |
60624 KB |
Output is correct |
39 |
Correct |
9 ms |
57688 KB |
Output is correct |
40 |
Correct |
8 ms |
57688 KB |
Output is correct |
41 |
Correct |
8 ms |
57688 KB |
Output is correct |
42 |
Correct |
163 ms |
58920 KB |
Output is correct |
43 |
Correct |
711 ms |
60620 KB |
Output is correct |
44 |
Correct |
477 ms |
58200 KB |
Output is correct |
45 |
Correct |
650 ms |
60612 KB |
Output is correct |
46 |
Correct |
390 ms |
58872 KB |
Output is correct |
47 |
Correct |
726 ms |
60968 KB |
Output is correct |
48 |
Correct |
786 ms |
60616 KB |
Output is correct |
49 |
Correct |
812 ms |
60632 KB |
Output is correct |
50 |
Correct |
811 ms |
60704 KB |
Output is correct |
51 |
Correct |
649 ms |
60700 KB |
Output is correct |
52 |
Correct |
747 ms |
60628 KB |
Output is correct |
53 |
Correct |
641 ms |
60860 KB |
Output is correct |
54 |
Correct |
643 ms |
60604 KB |
Output is correct |
55 |
Correct |
10 ms |
57688 KB |
Output is correct |
56 |
Incorrect |
88 ms |
60596 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
57688 KB |
Output is correct |
2 |
Correct |
8 ms |
57688 KB |
Output is correct |
3 |
Correct |
134 ms |
59984 KB |
Output is correct |
4 |
Correct |
831 ms |
60612 KB |
Output is correct |
5 |
Correct |
722 ms |
59116 KB |
Output is correct |
6 |
Correct |
788 ms |
60620 KB |
Output is correct |
7 |
Correct |
632 ms |
59592 KB |
Output is correct |
8 |
Correct |
779 ms |
60596 KB |
Output is correct |
9 |
Correct |
9 ms |
57688 KB |
Output is correct |
10 |
Correct |
8 ms |
57688 KB |
Output is correct |
11 |
Correct |
8 ms |
57688 KB |
Output is correct |
12 |
Correct |
8 ms |
57688 KB |
Output is correct |
13 |
Incorrect |
9 ms |
57940 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |