Submission #478233

#	Time	Username	Problem	Language	Result	Execution time	Memory
478233		khoabright	Rainforest Jumps (APIO21_jumps)	C++17	60 / 100	4027 ms	50480 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define mp make_pair

const int N = 2e5 + 5;
const int k = 19;

int L[N][20], R[N][20], higher[N][20], h[N];
int my_size;
bool sub1 = 1;

void cal_LR() {
    rep(i, 1, my_size) if (h[i] != i) {
        sub1 = 0;
        break;
    }
    
    stack<int> st;

    rep(i, 1, my_size) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        if (!st.empty()) L[i][0] = st.top();

        st.push(i);
    }

    while (!st.empty()) st.pop();

    rep1(i, my_size, 1) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        if (!st.empty()) R[i][0] = st.top();

        st.push(i);
    }

    rep(i, 1, my_size) {
        if (h[L[i][0]] > h[R[i][0]]) higher[i][0] = L[i][0];
        else higher[i][0] = R[i][0];
        if (h[higher[i][0]] < h[i]) higher[i][0] = 0;
    }

    rep(u, 1, k) {
        rep(i, 1, my_size) {
            L[i][u] = L[L[i][u - 1]][u - 1];
            R[i][u] = R[R[i][u - 1]][u - 1];
            higher[i][u] = higher[higher[i][u - 1]][u - 1];
        }
    }
}

int minimum_jumps_sub1234(int a, int b, int c, int d) {
    if (sub1) return c - b;
    ++a, ++b, ++c, ++d;
    queue<pii> q;
    vector<bool> vst(my_size + 1);
    vst[0] = 1;

    rep(i, a, b) q.push({i, 0}), vst[i] = 1;

    while (!q.empty()) {
        auto [u, w] = q.front();
        q.pop();
        if (c <= u && u <= d) return w;
        int v = L[u][0];
        if (!vst[v]) {
            q.push({v, w + 1});
            vst[v] = 1;
        }
        v = R[u][0];
        if (!vst[v]) {
            q.push({v, w + 1});
            vst[v] = 1;
        }
    }

    return -1;
}

int minimum_jumps_sub5(int s, int t) {
    ++s, ++t;
    //cout<<"s,t="<<s<<' '<<t<<'\n';

    int ans = 0;
    // cout << "s,t="<<s<<' '<<t<<'\n';
    // cout << "H,L,R="<<higher[s][0] << ' ' << L[s][0] << ' ' << R[s][0] <<' '<<
    ' '<<higher[t][0]<<' '<<L[t][0]<<' '<<R[t][0]<< '\n';
    rep1(u, k, 0) {
        if (higher[s][u] != 0 && h[higher[s][u]] <= h[t]) {
            //cout<<"u,higher="<<u<<' '<<higher[s][u]<<'\n';
            ans += (1 << u);
            s = higher[s][u];
        }
    }

    if (s != t) {
        //cout << "s,ans,R0="<<s<<' '<<ans<<' '<<R[s][0]<<'\n';
        rep1(u, k, 0) {
            if (R[s][u] != 0 && h[R[s][u]] <= h[t]) {
                ans += (1 << u);
                s = R[s][u];
            }
        }
    }

    if (s != t) {
        return -1;
    }
    else return ans;
}

int minimum_jumps_sub6(int a, int b, int c, int d) {
    ++a, ++b, ++c, ++d;
    int cur = b;
    rep1(i, b - 1, a) {
        if (h[i] > h[cur]) {
            if (h[i] > h[c]) {
                if (h[cur] < h[c]) {
                    return minimum_jumps_sub5(cur - 1, c - 1);
                }
                else return -1;
            }
            cur = i;
        }
    }
    //cout<<"cur="<<cur<<'\n';
    if (h[cur] > h[c]) return -1;
    return minimum_jumps_sub5(cur - 1, c - 1);
} 

int minimum_jumps(int a, int b, int c, int d) {
    if (a == b && c == d) return minimum_jumps_sub5(a, c);
    else if (c == d) return minimum_jumps_sub6(a, b, c, d);
    else return minimum_jumps_sub1234(a, b, c, d);
}

void init(int sz, vector<int> array) {
    my_size = sz;
    rep(i, 1, my_size) h[i] = array[i - 1];   
    cal_LR();
}

// int main() {
//     // ios_base::sync_with_stdio(0);
//     // cin.tie(0); cout.tie(0);

//     int x; cin >> x;
//     vector<int> array(x);
//     rep(i, 1, x) cin >> array[i - 1];
//     init(x,array);

//     //rep(i, 1, my_size) cout << L[i] << ' ' << R[i]<< '\n';

//     int q; cin >> q;
//     while (q--) {
//         int A, B, C, D;
//         cin >> A >> B >> C >> D;
//         cout << minimum_jumps_sub6(A,B,C,D) << '\n';
//     }
// }

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps_sub5(int, int)':
jumps.cpp:93:22: warning: left shift count >= width of type [-Wshift-count-overflow]
   93 |     ' '<<higher[t][0]<<' '<<L[t][0]<<' '<<R[t][0]<< '\n';
      |     ~~~~~~~~~~~~~~~~~^~~~~
jumps.cpp:93:36: warning: left shift count >= width of type [-Wshift-count-overflow]
   93 |     ' '<<higher[t][0]<<' '<<L[t][0]<<' '<<R[t][0]<< '\n';
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
jumps.cpp:93:50: warning: statement has no effect [-Wunused-value]
   93 |     ' '<<higher[t][0]<<' '<<L[t][0]<<' '<<R[t][0]<< '\n';
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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