#include "jumps.h"
// all the includes you need here
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <bitset>
#include <deque>
#include <iomanip>
#include <numeric>
#include <functional>
#include <complex>
#include <random>
#include <chrono>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<ld, ld> pld;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<pld> vpld;
typedef vector<string> vs;
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define rrep(i, a, b) for (int i = (b) - 1; i >= a; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define trav(a, x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define pq priority_queue
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl;
#define debug2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define debug3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define debug4(x, y, z, w) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << endl;
#define debug5(x, y, z, w, t) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << endl;
#define debug6(x, y, z, w, t, u) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << endl;
#define debug7(x, y, z, w, t, u, v) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << endl;
#define debug8(x, y, z, w, t, u, v, k) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << ", " << #k << " = " << k << endl;
#define debug9(x, y, z, w, t, u, v, k, l) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << ", " << #k << " = " << k << ", " << #l << " = " << l << endl;
const int N = 2e5 + 7;
const int LG = 22;
ll n;
vii a;
int lft[N], rgt[N];
// high[i] = the index of max(lft[i], rgh[i]), low[i] = the index of min(lft[i], rgh[i])
int high[N], low[N];
// uph[i][j] = high[high[...[i]]] (2^j times), upl[i][j] = low[low[...[i]]] (2^j times)
int uph[N][LG], upl[N][LG];
// a function to find for each index i, the greatest index j such that j <= i and a[j] > a[i]
void find_left() {
stack<int> st;
rep(i, 0, n) {
while (!st.empty() && a[st.top()] <= a[i]) {
st.pop();
}
if (st.empty()) {
lft[i] = -1;
} else {
lft[i] = st.top();
}
st.push(i);
}
}
// a function to find for each index i, the smallest index j such that j >= i and a[j] > a[i]
void find_right() {
stack<int> st;
rrep(i, 0, n) {
while (!st.empty() && a[st.top()] <= a[i]) {
st.pop();
}
if (st.empty()) {
rgt[i] = n;
} else {
rgt[i] = st.top();
}
st.push(i);
}
}
// a function to calculate the high and low arrays
void calc_high_low() {
rep(i, 0, n) {
if (lft[i] == -1 && rgt[i] == n) {
high[i] = -1;
low[i] = -1;
} else if (lft[i] == -1) {
high[i] = rgt[i];
low[i] = rgt[i];
} else if (rgt[i] == n) {
high[i] = lft[i];
low[i] = lft[i];
} else {
if (a[lft[i]] > a[rgt[i]]) {
high[i] = lft[i];
low[i] = rgt[i];
} else {
high[i] = rgt[i];
low[i] = lft[i];
}
}
}
}
// a function to calculate the sparse table for high and low
void calc_sparse() {
rep(i, 0, n) {
uph[i][0] = high[i];
upl[i][0] = low[i];
}
rep(j, 1, LG) {
rep(i, 0, n) {
if (uph[i][j - 1] == -1) {
uph[i][j] = -1;
} else {
uph[i][j] = uph[uph[i][j - 1]][j - 1];
}
if (upl[i][j - 1] == -1) {
upl[i][j] = -1;
} else {
upl[i][j] = upl[upl[i][j - 1]][j - 1];
}
}
}
}
// a function to go up from an index i by moving on the high array until we reach an index j such that a[j] > x
int go_up_high(int i, int x, int& cnt) {
//cout<<"CALLED: "<<i<<" "<<x<<endl;
if (i == -1) {
return -1;
}
if (a[i] > x) {
return -1;
}
if(a[i]==x){
return i;
}
rrep(j, 0, LG - 1) {
if (uph[i][j] == -1) {
continue;
}
if (a[uph[i][j]] <= x) {
i = uph[i][j];
cnt += (1 << j);
}
}
return i;
}
// a function to go up from an index i by moving on the low array until we reach an index j such that a[j] > x
int go_up_low(int i, int x, int& cnt) {
if (i == -1) {
return -1;
}
if (a[i] > x) {
return -1;
}
if(a[i]==x){
return i;
}
rrep(j, 0, LG - 1) {
if (upl[i][j] == -1) {
continue;
}
if (a[upl[i][j]] <= x) {
i = upl[i][j];
cnt += (1 << j);
}
}
return i;
}
void init(int N, std::vector<int> H) {
n = N;
a = H;
find_left();
find_right();
calc_high_low();
calc_sparse();
}
int minimum_jumps(int A, int B, int C, int D) {
if(A==B && C==D){
if(B==C){
return 0;
}
int cnt=0;
int x = go_up_high(B, a[C], cnt);
int y = go_up_low(x, a[C], cnt);
// debug2(x, y);
// debug(cnt);
// for(int i=0;i<n;i++){
// debug6(i, a[i], lft[i], rgt[i], high[i], low[i]);
// }
// // debug the uph and upl arrays
// rep(i, 0, n) {
// rep(j, 0, LG) {
// debug3(i, j, uph[i][j]);
// }
// }
if(a[y]==a[C]){
return cnt;
}
return -1;
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Incorrect |
164 ms |
32240 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
208 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
208 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
273 ms |
18476 KB |
Output is correct |
5 |
Correct |
1010 ms |
40136 KB |
Output is correct |
6 |
Correct |
606 ms |
6864 KB |
Output is correct |
7 |
Correct |
1010 ms |
40216 KB |
Output is correct |
8 |
Correct |
523 ms |
13980 KB |
Output is correct |
9 |
Correct |
1008 ms |
40096 KB |
Output is correct |
10 |
Correct |
986 ms |
40320 KB |
Output is correct |
11 |
Correct |
1108 ms |
40368 KB |
Output is correct |
12 |
Correct |
746 ms |
40336 KB |
Output is correct |
13 |
Correct |
891 ms |
40140 KB |
Output is correct |
14 |
Correct |
921 ms |
40632 KB |
Output is correct |
15 |
Correct |
1042 ms |
40988 KB |
Output is correct |
16 |
Correct |
920 ms |
41016 KB |
Output is correct |
17 |
Correct |
0 ms |
336 KB |
Output is correct |
18 |
Correct |
0 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
2 ms |
336 KB |
Output is correct |
21 |
Correct |
3 ms |
336 KB |
Output is correct |
22 |
Correct |
3 ms |
336 KB |
Output is correct |
23 |
Correct |
3 ms |
336 KB |
Output is correct |
24 |
Correct |
2 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
17 ms |
720 KB |
Output is correct |
28 |
Correct |
16 ms |
720 KB |
Output is correct |
29 |
Correct |
16 ms |
720 KB |
Output is correct |
30 |
Correct |
17 ms |
720 KB |
Output is correct |
31 |
Correct |
16 ms |
720 KB |
Output is correct |
32 |
Correct |
0 ms |
336 KB |
Output is correct |
33 |
Correct |
60 ms |
23368 KB |
Output is correct |
34 |
Correct |
98 ms |
40216 KB |
Output is correct |
35 |
Correct |
87 ms |
40348 KB |
Output is correct |
36 |
Correct |
92 ms |
40220 KB |
Output is correct |
37 |
Correct |
107 ms |
40612 KB |
Output is correct |
38 |
Correct |
101 ms |
40996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
273 ms |
18476 KB |
Output is correct |
5 |
Correct |
1010 ms |
40136 KB |
Output is correct |
6 |
Correct |
606 ms |
6864 KB |
Output is correct |
7 |
Correct |
1010 ms |
40216 KB |
Output is correct |
8 |
Correct |
523 ms |
13980 KB |
Output is correct |
9 |
Correct |
1008 ms |
40096 KB |
Output is correct |
10 |
Correct |
986 ms |
40320 KB |
Output is correct |
11 |
Correct |
1108 ms |
40368 KB |
Output is correct |
12 |
Correct |
746 ms |
40336 KB |
Output is correct |
13 |
Correct |
891 ms |
40140 KB |
Output is correct |
14 |
Correct |
921 ms |
40632 KB |
Output is correct |
15 |
Correct |
1042 ms |
40988 KB |
Output is correct |
16 |
Correct |
920 ms |
41016 KB |
Output is correct |
17 |
Correct |
0 ms |
336 KB |
Output is correct |
18 |
Correct |
0 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
2 ms |
336 KB |
Output is correct |
21 |
Correct |
3 ms |
336 KB |
Output is correct |
22 |
Correct |
3 ms |
336 KB |
Output is correct |
23 |
Correct |
3 ms |
336 KB |
Output is correct |
24 |
Correct |
2 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
17 ms |
720 KB |
Output is correct |
28 |
Correct |
16 ms |
720 KB |
Output is correct |
29 |
Correct |
16 ms |
720 KB |
Output is correct |
30 |
Correct |
17 ms |
720 KB |
Output is correct |
31 |
Correct |
16 ms |
720 KB |
Output is correct |
32 |
Correct |
0 ms |
336 KB |
Output is correct |
33 |
Correct |
60 ms |
23368 KB |
Output is correct |
34 |
Correct |
98 ms |
40216 KB |
Output is correct |
35 |
Correct |
87 ms |
40348 KB |
Output is correct |
36 |
Correct |
92 ms |
40220 KB |
Output is correct |
37 |
Correct |
107 ms |
40612 KB |
Output is correct |
38 |
Correct |
101 ms |
40996 KB |
Output is correct |
39 |
Correct |
0 ms |
336 KB |
Output is correct |
40 |
Correct |
0 ms |
336 KB |
Output is correct |
41 |
Correct |
0 ms |
336 KB |
Output is correct |
42 |
Correct |
285 ms |
18460 KB |
Output is correct |
43 |
Correct |
1014 ms |
40104 KB |
Output is correct |
44 |
Correct |
617 ms |
6864 KB |
Output is correct |
45 |
Correct |
915 ms |
40220 KB |
Output is correct |
46 |
Correct |
553 ms |
14032 KB |
Output is correct |
47 |
Correct |
940 ms |
40108 KB |
Output is correct |
48 |
Correct |
1118 ms |
40356 KB |
Output is correct |
49 |
Correct |
902 ms |
40288 KB |
Output is correct |
50 |
Correct |
1145 ms |
40364 KB |
Output is correct |
51 |
Correct |
998 ms |
40140 KB |
Output is correct |
52 |
Correct |
1102 ms |
40616 KB |
Output is correct |
53 |
Correct |
998 ms |
40996 KB |
Output is correct |
54 |
Correct |
948 ms |
41044 KB |
Output is correct |
55 |
Correct |
1 ms |
336 KB |
Output is correct |
56 |
Incorrect |
144 ms |
39988 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Incorrect |
164 ms |
32240 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |