#include "jumps.h" #include <vector> using namespace std; const int N = 200000; typedef vector<int> vi; int max(int a, int b) { return a > b ? a : b; } int ll[N], rr[N], qu[N], n, special; void init(int n_, vi hh) { int i, cnt; n = n_; special = 1; for (i = 0; i < n; i++) if (hh[i] != i + 1) { special = 0; break; } cnt = 0; for (i = 0; i < n; i++) { while (cnt && hh[qu[cnt - 1]] < hh[i]) cnt--; ll[i] = cnt == 0 ? -1 : qu[cnt - 1]; qu[cnt++] = i; } cnt = 0; for (i = n - 1; i >= 0; i--) { while (cnt && hh[qu[cnt - 1]] < hh[i]) cnt--; rr[i] = cnt == 0 ? -1 : qu[cnt - 1]; qu[cnt++] = i; } } int dd[N]; int minimum_jumps(int i1, int j1, int i2, int j2) { if (special) return i2 - j1; else { int head, cnt, i; for (i = 0; i < n; i++) dd[i] = n; head = cnt = 0; for (i = i1; i <= j1; i++) dd[i] = 0, qu[head + cnt++] = i; while (cnt) { int d; i = qu[cnt--, head++], d = dd[i] + 1; if (i2 <= i && i <= j2) return dd[i]; if (ll[i] != -1 && dd[ll[i]] > d) dd[ll[i]] = d, qu[head + cnt++] = ll[i]; if (rr[i] != -1 && dd[rr[i]] > d) dd[rr[i]] = d, qu[head + cnt++] = rr[i]; } return -1; } }