oj.uz

Submission #478421

# Submission time Handle Problem Language Result Execution time Memory
478421 2021-10-07T10:41:22 Z khoabright Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1349 ms 66112 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];
        }
    }

    int ans = 0;

    rep1(u, k, 0) {
        int tmp = higher[b][u];
        if (tmp != 0 && h[tmp] <= obstacle) {
            ans += (1 << u);
            b = tmp;
        }
    }

    if (h[b] == obstacle) {
        int tmp = R[b][0];
        if (tmp <= d) return ans + 1;
        return -1;
    }

    int left = L[b][0];
    if (left != 0 && R[left][0] <= d) {
        return ans + 2;
    }

    rep1(u, k, 0) {
        int tmp = R[b][u];
        if (tmp != 0 && tmp < c) {
            ans += (1 << u);
            b = tmp;
        }
    }

    if (c <= R[b][0] && R[b][0] <= d) return ans + 1;
    return -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 35 ms 15944 KB Output is correct
2 Correct 33 ms 15944 KB Output is correct
3 Correct 246 ms 55812 KB Output is correct
4 Correct 1349 ms 65984 KB Output is correct
5 Correct 1038 ms 41208 KB Output is correct
6 Correct 1170 ms 66112 KB Output is correct
7 Correct 945 ms 50112 KB Output is correct
8 Correct 1336 ms 65984 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15944 KB Output is correct
2 Correct 37 ms 15944 KB Output is correct
3 Correct 36 ms 15960 KB Output is correct
4 Correct 39 ms 16072 KB Output is correct
5 Incorrect 38 ms 15944 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15944 KB Output is correct
2 Correct 37 ms 15944 KB Output is correct
3 Correct 36 ms 15960 KB Output is correct
4 Correct 39 ms 16072 KB Output is correct
5 Incorrect 38 ms 15944 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15944 KB Output is correct
2 Correct 40 ms 15944 KB Output is correct
3 Correct 35 ms 15960 KB Output is correct
4 Incorrect 339 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 36 ms 15944 KB Output is correct
2 Correct 40 ms 15944 KB Output is correct
3 Correct 35 ms 15960 KB Output is correct
4 Incorrect 339 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 35 ms 15944 KB Output is correct
2 Correct 33 ms 15944 KB Output is correct
3 Correct 246 ms 55812 KB Output is correct
4 Correct 1349 ms 65984 KB Output is correct
5 Correct 1038 ms 41208 KB Output is correct
6 Correct 1170 ms 66112 KB Output is correct
7 Correct 945 ms 50112 KB Output is correct
8 Correct 1336 ms 65984 KB Output is correct
9 Correct 35 ms 15944 KB Output is correct
10 Correct 37 ms 15944 KB Output is correct
11 Correct 36 ms 15960 KB Output is correct
12 Correct 39 ms 16072 KB Output is correct
13 Incorrect 38 ms 15944 KB Output isn't correct
14 Halted 0 ms 0 KB -