#include <bits/stdc++.h>
using namespace std;
#include "jumps.h"
#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
#define FI first
#define SE second
#define MP make_pair
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;
#define INF 1000000005
#define MAXN 200005
#define MAXL 20
int n;
vi h;
int p[2][MAXL][MAXN];
ii sp[2][MAXL][MAXN];
inline ii qsp(bool b, int s, int e) {
int k = 31 - __builtin_clz(e - s + 1);
return max(sp[b][k][s], sp[b][k][e - (1 << k) + 1]);
}
void init(int _n, vi _h) {
n = _n;
h = _h;
{
stack<int> stk;
REP (i, 0, n) {
while (!stk.empty() && h[stk.top()] < h[i]) {
stk.pop();
}
if (!stk.empty()) {
p[0][0][i] = stk.top();
} else {
p[0][0][i] = -1;
}
stk.push(i);
}
}
{
stack<int> stk;
RREP (i, n - 1, 0) {
while (!stk.empty() && h[stk.top()] < h[i]) {
stk.pop();
}
if (!stk.empty()) {
p[1][0][i] = stk.top();
} else {
p[1][0][i] = -1;
}
stk.push(i);
}
}
REP (i, 0, n) {
if (p[0][0][i] == -1) {
swap(p[0][0][i], p[1][0][i]);
}
if (p[1][0][i] != -1) {
if (h[p[0][0][i]] < h[p[1][0][i]]) {
swap(p[0][0][i], p[1][0][i]);
}
}
}
REP (z, 0, 2) {
REP (k, 1, MAXL) {
REP (i, 0, n) {
if (p[z][k - 1][i] == -1) {
p[z][k][i] = -1;
} else {
p[z][k][i] = p[z][k - 1][p[z][k - 1][i]];
}
}
}
}
REP (i, 0, n) {
sp[0][0][i] = sp[1][0][i] = MP(h[i], i);
}
REP (k, 1, MAXL) {
REP (i, 0, n - (1 << k - 1)) {
sp[0][k][i] = max(sp[0][k - 1][i], sp[0][k - 1][i + (1 << k - 1)]);
sp[1][k][i] = min(sp[1][k - 1][i], sp[1][k - 1][i + (1 << k - 1)]);
}
}
}
ii jump(bool b, int u, int mx, int s = 0, int e = n - 1) {
int pc = 0;
RREP (k, MAXL - 1, 0) {
if (p[b][k][u] < s || p[b][k][u] > e) continue;
if (h[p[b][k][u]] <= mx) {
u = p[b][k][u];
pc += 1 << k;
}
}
return MP(u, pc);
}
int minimum_jumps(int a, int b, int c, int d) {
int rmx = qsp(0, c, d).FI, mmx = qsp(0, b + 1, c - 1).FI;
int u, pc;
u = qsp(1, a, b).SE;
if (mmx > rmx || h[u] > rmx) {
return -1;
}
int res = 0;
tie(u, pc) = jump(0, u, mmx - 1, a, b);
tie(u, pc) = jump(1, u, mmx - 1, a, b);
tie(u, pc) = jump(0, u, mmx - 1);
res += pc;
pc = 0;
assert(h[p[0][0][u]] >= mmx);
if (p[0][0][u] != -1 && h[p[0][0][u]] <= rmx) {
u = p[0][0][u];
pc++;
} else {
RREP (k, MAXL - 1, 0) {
if (p[1][k][u] == -1) continue;
if (h[p[1][k][u]] <= mmx - 1) {
u = p[1][k][u];
pc += 1 << k;
}
}
u = p[1][0][u];
pc++;
}
assert(h[u] >= mmx && h[u] <= rmx && u < c);
res += c + 1;
return res;
}
Compilation message
jumps.cpp: In function 'void init(int, vi)':
jumps.cpp:93:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
93 | REP (i, 0, n - (1 << k - 1)) {
| ~~^~~
jumps.cpp:5:42: note: in definition of macro 'REP'
5 | #define REP(i, j, k) for (int i = j; i < k; i++)
| ^
jumps.cpp:94:73: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
94 | sp[0][k][i] = max(sp[0][k - 1][i], sp[0][k - 1][i + (1 << k - 1)]);
| ~~^~~
jumps.cpp:95:73: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
95 | sp[1][k][i] = min(sp[1][k - 1][i], sp[1][k - 1][i + (1 << k - 1)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
832 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
800 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
800 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
832 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
