#include "jumps.h"
#include <vector>
#include <iostream>
#include <stack>
using namespace std;
const int maxN = 200'000;
const int logN = 18;
const int INF = 1e9;
int N;
vector<int> H(2+maxN);
vector<int> leftHigh(2+maxN);
vector<int> rightHigh(2+maxN);
vector< vector<int> > highEdge(2+maxN, vector<int>(logN));
vector< vector<int> > lowEdge(2+maxN, vector<int>(logN));
vector< vector<int> > rightEdge(2+maxN, vector<int>(logN));
vector< vector<int> > highEdge_highmax(2+maxN, vector<int>(logN));
vector< vector<int> > highEdge_lowmax(2+maxN, vector<int>(logN));
struct segtree
{
int l;
int r;
int mn = -INF;
int mx = INF;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
{
mn = mx = H[l];
}
else
{
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
mn = min(left->mn, right->mn);
mx = max(left->mx, right->mx);
}
}
int rangemax(int L, int R)
{
if(R < l || r < L) return -INF;
else if(L <= l && r <= R) return mx;
else return max(left->rangemax(L, R), right->rangemax(L, R));
}
int rangemin(int L, int R)
{
if(R < l || r < L) return INF;
else if(L <= l && r <= R) return mn;
else return min(left->rangemin(L, R), right->rangemin(L, R));
}
};
segtree ST;
void init(int n, vector<int> h)
{
N = n;
H[0] = H[N+1] = INF;
for(int i = 1; i <= N; i++) H[i] = h[i-1];
stack<int> S;
leftHigh[0] = 0;
S.push(0);
for(int i = 1; i <= N; i++)
{
while(!S.empty() && H[S.top()] < H[i])
S.pop();
if(!S.empty()) leftHigh[i] = S.top();
S.push(i);
}
while(!S.empty()) S.pop();
leftHigh[N+1] = N+1;
rightHigh[N+1] = N+1;
S.push(N+1);
for(int i = N; i >= 1; i--)
{
while(!S.empty() && H[S.top()] < H[i])
S.pop();
if(!S.empty()) rightHigh[i] = S.top();
S.push(i);
}
leftHigh[0] = 0;
// for(int i = 0; i <= N+1; i++) cerr << leftHigh[i] << ' ';
// cerr << '\n';
// for(int i = 0; i <= N+1; i++) cerr << rightHigh[i] << ' ';
// cerr << '\n';
highEdge[0][0] = 0;
lowEdge[0][0] = 0;
rightEdge[0][0] = 0;
highEdge_highmax[0][0] = 0;
highEdge_lowmax[0][0] = 0;
for(int i = 1; i <= N; i++)
{
highEdge[i][0] = (H[ leftHigh[i] ] > H[ rightHigh[i] ]) ? leftHigh[i] : rightHigh[i];
lowEdge[i][0] = (H[ leftHigh[i] ] < H[ rightHigh[i] ]) ? leftHigh[i] : rightHigh[i];
rightEdge[i][0] = rightHigh[i];
}
for(int i = 1; i <= N; i++)
{
highEdge_highmax[i][0] = highEdge[i][0];
highEdge_lowmax[i][0] = lowEdge[i][0];
}
highEdge[N+1][0] = N+1;
lowEdge[N+1][0] = N+1;
rightEdge[N+1][0] = N+1;
highEdge_highmax[N+1][0] = N+1;
highEdge_lowmax[N+1][0] = N+1;
for(int e = 1; e < logN; e++)
{
for(int i = 0; i <= N+1; i++)
{
highEdge[i][e] = highEdge[ highEdge[i][e-1] ][e-1];
lowEdge[i][e] = lowEdge[ lowEdge[i][e-1] ][e-1];
rightEdge[i][e] = rightEdge[ rightEdge[i][e-1] ][e-1];
highEdge_highmax[i][e] = max(highEdge_highmax[i][e-1], highEdge_highmax[ highEdge[i][e-1] ][e-1]);
highEdge_lowmax[i][e] = max(highEdge_lowmax[i][e-1], highEdge_lowmax[ highEdge[i][e-1] ][e-1]);
}
}
ST = segtree(0, N+1);
}
int minimum_jumps(int A, int B, int C, int D)
{
A++;
B++;
C++;
D++;
int oldB = B;
int CDmax = ST.rangemax(C, D);
if(ST.rangemax(B, oldB) > CDmax) return -1;
while(A != B)
{
int m = (A+B)/2;
if(ST.rangemax(m, oldB) <= CDmax) B = m;
else A = m+1;
}
for(int bit = logN-1; bit >= 0; bit--)
{
int newA = A + (1 << bit);
if(newA > oldB) continue;
if(ST.rangemax(A, oldB) == ST.rangemax(newA, oldB)) A = newA;
}
// cerr << "A = B = " << A << '\n';
int o = A;
int res = 0;
// while(1)
// {
// if(C <= o && o <= D) return res;
// else if(o > D || H[o] > CDmax) return -1;
// else if(highEdge[o][0] < C && H[highEdge[o][0]] <= CDmax && lowEdge[o][0] < C)
// {
// o = highEdge[o][0];
// res++;
// }
// else
// {
// o = rightEdge[o][0];
// res++;
// }
// }
for(int bit = logN-1; bit >= 0; bit--)
{
if(C <= o && o <= D) return res;
else if(o > D || H[o] > CDmax) return -1;
else if(highEdge_highmax[o][bit] < C && H[highEdge[o][bit]] <= CDmax && highEdge_lowmax[o][0] < C)
{
o = highEdge[o][bit];
res += (1 << bit);
}
}
for(int bit = logN-1; bit >= 0; bit--)
{
if(C <= o && o <= D) return res;
else if(o > D || H[o] > CDmax) return -1;
else if(rightEdge[o][bit] < C)
{
o = rightEdge[o][bit];
res += (1 << bit);
}
}
if(o < C)
{
o = rightEdge[o][0];
res++;
}
if(D < o) return -1;
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
104388 KB |
Output is correct |
2 |
Correct |
86 ms |
104412 KB |
Output is correct |
3 |
Correct |
577 ms |
121328 KB |
Output is correct |
4 |
Correct |
2910 ms |
125504 KB |
Output is correct |
5 |
Correct |
2205 ms |
114976 KB |
Output is correct |
6 |
Correct |
2778 ms |
125528 KB |
Output is correct |
7 |
Correct |
2526 ms |
118848 KB |
Output is correct |
8 |
Correct |
3534 ms |
125548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
104372 KB |
Output is correct |
2 |
Correct |
105 ms |
104348 KB |
Output is correct |
3 |
Correct |
109 ms |
104280 KB |
Output is correct |
4 |
Correct |
112 ms |
104412 KB |
Output is correct |
5 |
Correct |
97 ms |
104356 KB |
Output is correct |
6 |
Correct |
92 ms |
104360 KB |
Output is correct |
7 |
Correct |
105 ms |
104432 KB |
Output is correct |
8 |
Correct |
108 ms |
104376 KB |
Output is correct |
9 |
Correct |
95 ms |
104384 KB |
Output is correct |
10 |
Incorrect |
97 ms |
104420 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
104372 KB |
Output is correct |
2 |
Correct |
105 ms |
104348 KB |
Output is correct |
3 |
Correct |
109 ms |
104280 KB |
Output is correct |
4 |
Correct |
112 ms |
104412 KB |
Output is correct |
5 |
Correct |
97 ms |
104356 KB |
Output is correct |
6 |
Correct |
92 ms |
104360 KB |
Output is correct |
7 |
Correct |
105 ms |
104432 KB |
Output is correct |
8 |
Correct |
108 ms |
104376 KB |
Output is correct |
9 |
Correct |
95 ms |
104384 KB |
Output is correct |
10 |
Incorrect |
97 ms |
104420 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
104400 KB |
Output is correct |
2 |
Correct |
88 ms |
104360 KB |
Output is correct |
3 |
Correct |
117 ms |
104340 KB |
Output is correct |
4 |
Correct |
88 ms |
104404 KB |
Output is correct |
5 |
Correct |
278 ms |
120772 KB |
Output is correct |
6 |
Correct |
316 ms |
124736 KB |
Output is correct |
7 |
Correct |
190 ms |
114816 KB |
Output is correct |
8 |
Correct |
290 ms |
124672 KB |
Output is correct |
9 |
Correct |
119 ms |
107452 KB |
Output is correct |
10 |
Correct |
286 ms |
124664 KB |
Output is correct |
11 |
Correct |
283 ms |
125504 KB |
Output is correct |
12 |
Correct |
282 ms |
125012 KB |
Output is correct |
13 |
Correct |
284 ms |
125248 KB |
Output is correct |
14 |
Correct |
296 ms |
124668 KB |
Output is correct |
15 |
Incorrect |
427 ms |
124688 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
104424 KB |
Output is correct |
2 |
Correct |
102 ms |
104456 KB |
Output is correct |
3 |
Correct |
88 ms |
104328 KB |
Output is correct |
4 |
Correct |
523 ms |
113684 KB |
Output is correct |
5 |
Correct |
1456 ms |
124668 KB |
Output is correct |
6 |
Correct |
1006 ms |
107768 KB |
Output is correct |
7 |
Correct |
1611 ms |
124712 KB |
Output is correct |
8 |
Correct |
902 ms |
111384 KB |
Output is correct |
9 |
Correct |
1439 ms |
124728 KB |
Output is correct |
10 |
Correct |
1456 ms |
125484 KB |
Output is correct |
11 |
Correct |
1793 ms |
124908 KB |
Output is correct |
12 |
Correct |
1639 ms |
125348 KB |
Output is correct |
13 |
Correct |
1417 ms |
124828 KB |
Output is correct |
14 |
Correct |
1685 ms |
124848 KB |
Output is correct |
15 |
Correct |
1093 ms |
124724 KB |
Output is correct |
16 |
Correct |
1240 ms |
124736 KB |
Output is correct |
17 |
Correct |
87 ms |
104384 KB |
Output is correct |
18 |
Correct |
85 ms |
104372 KB |
Output is correct |
19 |
Correct |
88 ms |
104404 KB |
Output is correct |
20 |
Correct |
90 ms |
104344 KB |
Output is correct |
21 |
Correct |
93 ms |
104432 KB |
Output is correct |
22 |
Correct |
96 ms |
104412 KB |
Output is correct |
23 |
Correct |
92 ms |
104436 KB |
Output is correct |
24 |
Correct |
92 ms |
104384 KB |
Output is correct |
25 |
Correct |
90 ms |
104396 KB |
Output is correct |
26 |
Correct |
90 ms |
104500 KB |
Output is correct |
27 |
Correct |
124 ms |
104608 KB |
Output is correct |
28 |
Correct |
119 ms |
104512 KB |
Output is correct |
29 |
Correct |
107 ms |
104496 KB |
Output is correct |
30 |
Correct |
115 ms |
104512 KB |
Output is correct |
31 |
Correct |
112 ms |
104680 KB |
Output is correct |
32 |
Correct |
91 ms |
104296 KB |
Output is correct |
33 |
Correct |
207 ms |
116160 KB |
Output is correct |
34 |
Correct |
289 ms |
124736 KB |
Output is correct |
35 |
Correct |
280 ms |
125360 KB |
Output is correct |
36 |
Correct |
283 ms |
124660 KB |
Output is correct |
37 |
Correct |
450 ms |
124780 KB |
Output is correct |
38 |
Correct |
272 ms |
124732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
104424 KB |
Output is correct |
2 |
Correct |
102 ms |
104456 KB |
Output is correct |
3 |
Correct |
88 ms |
104328 KB |
Output is correct |
4 |
Correct |
523 ms |
113684 KB |
Output is correct |
5 |
Correct |
1456 ms |
124668 KB |
Output is correct |
6 |
Correct |
1006 ms |
107768 KB |
Output is correct |
7 |
Correct |
1611 ms |
124712 KB |
Output is correct |
8 |
Correct |
902 ms |
111384 KB |
Output is correct |
9 |
Correct |
1439 ms |
124728 KB |
Output is correct |
10 |
Correct |
1456 ms |
125484 KB |
Output is correct |
11 |
Correct |
1793 ms |
124908 KB |
Output is correct |
12 |
Correct |
1639 ms |
125348 KB |
Output is correct |
13 |
Correct |
1417 ms |
124828 KB |
Output is correct |
14 |
Correct |
1685 ms |
124848 KB |
Output is correct |
15 |
Correct |
1093 ms |
124724 KB |
Output is correct |
16 |
Correct |
1240 ms |
124736 KB |
Output is correct |
17 |
Correct |
87 ms |
104384 KB |
Output is correct |
18 |
Correct |
85 ms |
104372 KB |
Output is correct |
19 |
Correct |
88 ms |
104404 KB |
Output is correct |
20 |
Correct |
90 ms |
104344 KB |
Output is correct |
21 |
Correct |
93 ms |
104432 KB |
Output is correct |
22 |
Correct |
96 ms |
104412 KB |
Output is correct |
23 |
Correct |
92 ms |
104436 KB |
Output is correct |
24 |
Correct |
92 ms |
104384 KB |
Output is correct |
25 |
Correct |
90 ms |
104396 KB |
Output is correct |
26 |
Correct |
90 ms |
104500 KB |
Output is correct |
27 |
Correct |
124 ms |
104608 KB |
Output is correct |
28 |
Correct |
119 ms |
104512 KB |
Output is correct |
29 |
Correct |
107 ms |
104496 KB |
Output is correct |
30 |
Correct |
115 ms |
104512 KB |
Output is correct |
31 |
Correct |
112 ms |
104680 KB |
Output is correct |
32 |
Correct |
91 ms |
104296 KB |
Output is correct |
33 |
Correct |
207 ms |
116160 KB |
Output is correct |
34 |
Correct |
289 ms |
124736 KB |
Output is correct |
35 |
Correct |
280 ms |
125360 KB |
Output is correct |
36 |
Correct |
283 ms |
124660 KB |
Output is correct |
37 |
Correct |
450 ms |
124780 KB |
Output is correct |
38 |
Correct |
272 ms |
124732 KB |
Output is correct |
39 |
Correct |
87 ms |
104344 KB |
Output is correct |
40 |
Correct |
93 ms |
104408 KB |
Output is correct |
41 |
Correct |
89 ms |
104412 KB |
Output is correct |
42 |
Correct |
510 ms |
113648 KB |
Output is correct |
43 |
Correct |
1582 ms |
124772 KB |
Output is correct |
44 |
Correct |
994 ms |
107740 KB |
Output is correct |
45 |
Correct |
1470 ms |
124736 KB |
Output is correct |
46 |
Correct |
955 ms |
111392 KB |
Output is correct |
47 |
Correct |
1500 ms |
124680 KB |
Output is correct |
48 |
Correct |
1432 ms |
125508 KB |
Output is correct |
49 |
Correct |
1679 ms |
124916 KB |
Output is correct |
50 |
Correct |
1591 ms |
125456 KB |
Output is correct |
51 |
Correct |
1526 ms |
124668 KB |
Output is correct |
52 |
Correct |
1889 ms |
124776 KB |
Output is correct |
53 |
Correct |
1370 ms |
124736 KB |
Output is correct |
54 |
Correct |
1363 ms |
124720 KB |
Output is correct |
55 |
Correct |
91 ms |
104512 KB |
Output is correct |
56 |
Correct |
383 ms |
124652 KB |
Output is correct |
57 |
Correct |
2164 ms |
124728 KB |
Output is correct |
58 |
Correct |
818 ms |
107964 KB |
Output is correct |
59 |
Correct |
1992 ms |
124736 KB |
Output is correct |
60 |
Correct |
832 ms |
111548 KB |
Output is correct |
61 |
Correct |
1769 ms |
124728 KB |
Output is correct |
62 |
Correct |
3111 ms |
125484 KB |
Output is correct |
63 |
Correct |
3296 ms |
124996 KB |
Output is correct |
64 |
Correct |
2705 ms |
125068 KB |
Output is correct |
65 |
Correct |
1727 ms |
124664 KB |
Output is correct |
66 |
Correct |
3008 ms |
124684 KB |
Output is correct |
67 |
Correct |
2050 ms |
124736 KB |
Output is correct |
68 |
Correct |
1356 ms |
124720 KB |
Output is correct |
69 |
Correct |
86 ms |
104360 KB |
Output is correct |
70 |
Correct |
89 ms |
104424 KB |
Output is correct |
71 |
Correct |
102 ms |
104356 KB |
Output is correct |
72 |
Correct |
108 ms |
104432 KB |
Output is correct |
73 |
Correct |
90 ms |
104352 KB |
Output is correct |
74 |
Correct |
89 ms |
104432 KB |
Output is correct |
75 |
Correct |
91 ms |
104408 KB |
Output is correct |
76 |
Correct |
85 ms |
104384 KB |
Output is correct |
77 |
Correct |
88 ms |
104296 KB |
Output is correct |
78 |
Correct |
88 ms |
104344 KB |
Output is correct |
79 |
Correct |
107 ms |
104436 KB |
Output is correct |
80 |
Correct |
87 ms |
104552 KB |
Output is correct |
81 |
Correct |
86 ms |
104304 KB |
Output is correct |
82 |
Correct |
90 ms |
104380 KB |
Output is correct |
83 |
Correct |
89 ms |
104384 KB |
Output is correct |
84 |
Correct |
85 ms |
104368 KB |
Output is correct |
85 |
Correct |
93 ms |
104440 KB |
Output is correct |
86 |
Correct |
117 ms |
104600 KB |
Output is correct |
87 |
Correct |
119 ms |
104608 KB |
Output is correct |
88 |
Correct |
139 ms |
104512 KB |
Output is correct |
89 |
Correct |
122 ms |
104672 KB |
Output is correct |
90 |
Correct |
113 ms |
104608 KB |
Output is correct |
91 |
Correct |
91 ms |
104404 KB |
Output is correct |
92 |
Correct |
89 ms |
104484 KB |
Output is correct |
93 |
Correct |
117 ms |
104824 KB |
Output is correct |
94 |
Correct |
109 ms |
104640 KB |
Output is correct |
95 |
Correct |
117 ms |
104676 KB |
Output is correct |
96 |
Correct |
99 ms |
104612 KB |
Output is correct |
97 |
Correct |
123 ms |
104652 KB |
Output is correct |
98 |
Correct |
107 ms |
104568 KB |
Output is correct |
99 |
Correct |
316 ms |
124656 KB |
Output is correct |
100 |
Correct |
298 ms |
124676 KB |
Output is correct |
101 |
Correct |
307 ms |
125304 KB |
Output is correct |
102 |
Correct |
288 ms |
124656 KB |
Output is correct |
103 |
Correct |
446 ms |
124848 KB |
Output is correct |
104 |
Correct |
283 ms |
124720 KB |
Output is correct |
105 |
Correct |
91 ms |
104368 KB |
Output is correct |
106 |
Correct |
209 ms |
116060 KB |
Output is correct |
107 |
Correct |
301 ms |
124660 KB |
Output is correct |
108 |
Correct |
311 ms |
125456 KB |
Output is correct |
109 |
Correct |
285 ms |
124732 KB |
Output is correct |
110 |
Correct |
436 ms |
124716 KB |
Output is correct |
111 |
Correct |
287 ms |
124744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
104388 KB |
Output is correct |
2 |
Correct |
86 ms |
104412 KB |
Output is correct |
3 |
Correct |
577 ms |
121328 KB |
Output is correct |
4 |
Correct |
2910 ms |
125504 KB |
Output is correct |
5 |
Correct |
2205 ms |
114976 KB |
Output is correct |
6 |
Correct |
2778 ms |
125528 KB |
Output is correct |
7 |
Correct |
2526 ms |
118848 KB |
Output is correct |
8 |
Correct |
3534 ms |
125548 KB |
Output is correct |
9 |
Correct |
96 ms |
104372 KB |
Output is correct |
10 |
Correct |
105 ms |
104348 KB |
Output is correct |
11 |
Correct |
109 ms |
104280 KB |
Output is correct |
12 |
Correct |
112 ms |
104412 KB |
Output is correct |
13 |
Correct |
97 ms |
104356 KB |
Output is correct |
14 |
Correct |
92 ms |
104360 KB |
Output is correct |
15 |
Correct |
105 ms |
104432 KB |
Output is correct |
16 |
Correct |
108 ms |
104376 KB |
Output is correct |
17 |
Correct |
95 ms |
104384 KB |
Output is correct |
18 |
Incorrect |
97 ms |
104420 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |