oj.uz

Submission #478315

# Submission time Handle Problem Language Result Execution time Memory
478315 2021-10-07T02:27:27 Z khoabright Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 57 ms 32092 KB 
#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], f[N][20];
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];
        }
    }

    rep(i, 1, my_size) {
        f[i][0] = h[i];
    }

    rep(u, 1, k) {
        int tmp = N - (1 << u) + 1;
        rep(i, 1, tmp - 1) {
            f[i][u] = max(f[i][u - 1], f[i + (1 << (u - 1))][u - 1]);
        }
    }
}

int get_max(int l, int r) {
    int k = log2(r - l + 1);
    return max(f[l][k],f[r - (1 << k) + 1][k]);
}

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;
 
    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];
        }
    }

    //cout<<"s,ans="<<s<<' '<<ans<<'\n';

    //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 (R[s][0] != t) {
        return -1;
    }
    else return ans + 1;
}

int minimum_jumps_sub7(int a, int b, int c, int d) {
    ++a, ++b, ++c, ++d;

    //cout<<"b,L="<<b<<' '<<L[b][0]<<'\n';
    int maxi = get_max(c, d);
    int obstacle = get_max(b + 1, c - 1);
    if (h[b] > maxi) return -1;
    rep1(u, k, 0) {
        if (L[b][u] >= a && h[L[b][u]] <= maxi) {
            b = L[b][u];
        }
    }

    obstacle = max(obstacle, h[b]);
    rep1(u, k, 0) {
        if (R[c][u] != 0 && R[c][u] <= d && h[R[c][u]] < obstacle) {
            c = R[c][u];
        }
    }
    if (h[c] < obstacle) c = R[c][0];

    return minimum_jumps_sub5(b - 1, c - 1);
} 

int minimum_jumps(int a, int b, int c, int d) {
    return minimum_jumps_sub7(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 l, r; cin >> l >> r;
//         // cout << get_max(l, r) << '\n';
//         int A, B, C, D;
//         cin >> A >> B >> C >> D;
//         cout << minimum_jumps_sub7(A,B,C,D) << '\n';
//     }
// }

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 32068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 32092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 32092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 32084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 32076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 32076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 32068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -