oj.uz

Submission #478318

# Submission time Handle Problem Language Result Execution time Memory
478318 2021-10-07T02:35:46 Z khoabright Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1385 ms 66044 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) {
    if (l > r) return 0;
    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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15944 KB Output is correct
2 Correct 34 ms 15960 KB Output is correct
3 Correct 203 ms 55832 KB Output is correct
4 Correct 1385 ms 66044 KB Output is correct
5 Correct 1122 ms 41240 KB Output is correct
6 Correct 1268 ms 65984 KB Output is correct
7 Correct 1057 ms 50240 KB Output is correct
8 Correct 1316 ms 65984 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15944 KB Output is correct
2 Correct 32 ms 15952 KB Output is correct
3 Correct 32 ms 15956 KB Output is correct
4 Correct 34 ms 15948 KB Output is correct
5 Correct 35 ms 15944 KB Output is correct
6 Incorrect 39 ms 16000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15944 KB Output is correct
2 Correct 32 ms 15952 KB Output is correct
3 Correct 32 ms 15956 KB Output is correct
4 Correct 34 ms 15948 KB Output is correct
5 Correct 35 ms 15944 KB Output is correct
6 Incorrect 39 ms 16000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15952 KB Output is correct
2 Correct 31 ms 15964 KB Output is correct
3 Correct 37 ms 15948 KB Output is correct
4 Correct 33 ms 15944 KB Output is correct
5 Correct 128 ms 55596 KB Output is correct
6 Correct 153 ms 65224 KB Output is correct
7 Correct 107 ms 41092 KB Output is correct
8 Incorrect 141 ms 65308 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15964 KB Output is correct
2 Correct 35 ms 16072 KB Output is correct
3 Correct 34 ms 15944 KB Output is correct
4 Incorrect 315 ms 38424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15964 KB Output is correct
2 Correct 35 ms 16072 KB Output is correct
3 Correct 34 ms 15944 KB Output is correct
4 Incorrect 315 ms 38424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15944 KB Output is correct
2 Correct 34 ms 15960 KB Output is correct
3 Correct 203 ms 55832 KB Output is correct
4 Correct 1385 ms 66044 KB Output is correct
5 Correct 1122 ms 41240 KB Output is correct
6 Correct 1268 ms 65984 KB Output is correct
7 Correct 1057 ms 50240 KB Output is correct
8 Correct 1316 ms 65984 KB Output is correct
9 Correct 36 ms 15944 KB Output is correct
10 Correct 32 ms 15952 KB Output is correct
11 Correct 32 ms 15956 KB Output is correct
12 Correct 34 ms 15948 KB Output is correct
13 Correct 35 ms 15944 KB Output is correct
14 Incorrect 39 ms 16000 KB Output isn't correct
15 Halted 0 ms 0 KB -