oj.uz

Submission #478426

# Submission time Handle Problem Language Result Execution time Memory
478426 2021-10-07T10:45:30 Z khoabright Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1183 ms 65984 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 || obstacle == 0) {
        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 34 ms 15944 KB Output is correct
2 Correct 37 ms 15956 KB Output is correct
3 Correct 267 ms 55840 KB Output is correct
4 Correct 1133 ms 65980 KB Output is correct
5 Correct 1086 ms 41116 KB Output is correct
6 Correct 1183 ms 65984 KB Output is correct
7 Correct 1008 ms 50108 KB Output is correct
8 Correct 1119 ms 65984 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15948 KB Output is correct
2 Correct 37 ms 15944 KB Output is correct
3 Correct 39 ms 15944 KB Output is correct
4 Correct 34 ms 15944 KB Output is correct
5 Incorrect 43 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 33 ms 15948 KB Output is correct
2 Correct 37 ms 15944 KB Output is correct
3 Correct 39 ms 15944 KB Output is correct
4 Correct 34 ms 15944 KB Output is correct
5 Incorrect 43 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 34 ms 15952 KB Output is correct
2 Correct 35 ms 15944 KB Output is correct
3 Correct 36 ms 15944 KB Output is correct
4 Correct 34 ms 15968 KB Output is correct
5 Incorrect 123 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 33 ms 15920 KB Output is correct
2 Correct 37 ms 15948 KB Output is correct
3 Correct 38 ms 15944 KB Output is correct
4 Incorrect 371 ms 38464 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15920 KB Output is correct
2 Correct 37 ms 15948 KB Output is correct
3 Correct 38 ms 15944 KB Output is correct
4 Incorrect 371 ms 38464 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15944 KB Output is correct
2 Correct 37 ms 15956 KB Output is correct
3 Correct 267 ms 55840 KB Output is correct
4 Correct 1133 ms 65980 KB Output is correct
5 Correct 1086 ms 41116 KB Output is correct
6 Correct 1183 ms 65984 KB Output is correct
7 Correct 1008 ms 50108 KB Output is correct
8 Correct 1119 ms 65984 KB Output is correct
9 Correct 33 ms 15948 KB Output is correct
10 Correct 37 ms 15944 KB Output is correct
11 Correct 39 ms 15944 KB Output is correct
12 Correct 34 ms 15944 KB Output is correct
13 Incorrect 43 ms 15944 KB Output isn't correct
14 Halted 0 ms 0 KB -