Submission #1041147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041147		underwaterkillerwhale	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	817 ms	84280 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for (auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 2e9;
const ll BASE = 137;

int n, A, B, C, D;
int a[N];
int spt[N][25], spt2[N][25];
pair<int,int> mx[N][25];
pair<int,int> nxt[N];

pair<int,int> get (int L, int R) {
    if (L > R) return {-INF, 0};
    int K = 31 - __builtin_clz(R - L + 1);
    return max(mx[L][K], mx[R - (1 << K) + 1][K]);
}

int minimum_jumps (int A, int B, int C, int D)  {
    ++A, ++B, ++C, ++ D;
    int X = get(C, D).fs;
    int bound; {
        int lf = A, rt = B;
        while (lf < rt) {
            int mid = lf + rt >> 1;
            if (get(mid, B).fs < X) rt = mid;
            else lf = mid + 1;
        }
        bound = lf;
    }
    if (get(bound, B).fs > X) {
        return -1;
    }
    if (get(B + 1, C - 1).fs > X) {
        return -1;
    }
    int pos = get(bound, B).se;
    ll res = 0;
    reb (i, 17, 0) {
        if (a[spt2[pos][i]] <= get(B + 1, C - 1).fs) {
            pos = spt2[pos][i];
            res += (1 << i);
        }
    }
    if (a[spt2[pos][0]] <= X && a[pos] < get(B + 1, C  - 1).fs) {
        ++res;
        pos = spt2[pos][0];
        if (pos < C) ++res;
        return res;
    }
    reb (i, 17, 0) {
        if (spt[pos][i] < C) {
            pos = spt[pos][i];
            res += (1 << i);
        }
    }
    ++res;
    return res;
}

//void solution() {
void init (int _n, vector<int> _a) {
//    cin >> n;
//    cin >> A >> B >> C >> D;
//    rep (i, 1, n) cin >> a[i];
    n = _n;
    rep (i, 1, n) a[i] = _a[i - 1];
    stack<pair<int,int>> st;
    rep (i, 1, n) {
        while (!st.empty() && st.top().se < a[i]) st.pop();
        if (st.empty()) nxt[i].fs = i;
        else nxt[i].fs = st.top().fs;
        st.push({i, a[i]});
    }
    stack<pair<int,int>> ().swap(st);
    reb (i, n, 1) {
        while (!st.empty() && st.top().se < a[i]) st.pop();
        if (st.empty()) nxt[i].se = i;
        else nxt[i].se = st.top().fs;
        st.push({i, a[i]});
    }
    rep (i, 1, n) {
        if (a[nxt[i].fs] > a[nxt[i].se]) swap (nxt[i].fs, nxt[i].se);
        spt[i][0] = max(nxt[i].fs, nxt[i].se);
        spt2[i][0] = nxt[i].se;
    }
    rep (j, 1, 17)
    rep (i, 1, n) spt[i][j] = spt[spt[i][j - 1]][j - 1], spt2[i][j] = spt2[spt2[i][j - 1]][j - 1];
    rep (i, 1, n) mx[i][0] = {a[i], i};
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
}

//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug challenge +2
7
3 2 1 6 4 5 7
*/

Compilation message (stderr)

jumps.cpp:110:1: warning: multi-line comment [-Wcomment]
  110 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:41:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |             int mid = lf + rt >> 1;
      |                       ~~~^~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:107:97: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  107 |         for (int i = 1; i + (1 << j) - 1 <= n; ++i) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
      |                                                                                               ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19