Submission #1041137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041137		underwaterkillerwhale	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	825 ms	84464 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;
//    cout << C<<" "<<D<<" "<<X<<"\n";
    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;
    }
//    cout <<bound<<" "<<"asdsad\n";
    if (get(bound, B).fs > X) {
        return -1;
    }
//    cout << B<<" "<<C<<" "<<get(B + 1, C - 1).fs<<"\n";
    if (get(B + 1, C - 1).fs > X) {
        return -1;
    }
    int pos = get(bound, B).se;
//    cout << pos <<"\n";
    ll res = 0;
    reb (i, 20, 0) {
//        cout << pos<<","<<i<<" "<<spt2[pos][i]<<" "<<get(B + 1, C - 1).fs<<"\n";
        if (a[spt2[pos][i]] <= get(B + 1, C - 1).fs) {
            pos = spt2[pos][i];
            res += (1LL << 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;
    }
//    cout << res <<" "<<pos<<"\n";
    reb (i, 20, 0) {
//        cout << pos <<" "<<i<<" "<<spt[pos][i] <<"\n";
        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;
//            cout << i<<" "<<nxt[i].fs <<"\n";
        }
        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;
//        cout << i <<" "<<nxt[i].fs << " "<<nxt[i].se <<"\n";
    }
    rep (j, 1, 20)
    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]);
//    cout << minimum_jumps(A, B, C, D);
}

//#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:122:1: warning: multi-line comment [-Wcomment]
  122 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             int mid = lf + rt >> 1;
      |                       ~~~^~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:118:97: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  118 |         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