oj.uz

Submission #478427

# Submission time Handle Problem Language Result Execution time Memory
478427 2021-10-07T10:46:54 Z khoabright Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1367 ms 66076 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 37 ms 15960 KB Output is correct
3 Correct 192 ms 55836 KB Output is correct
4 Correct 1324 ms 65984 KB Output is correct
5 Correct 1089 ms 41140 KB Output is correct
6 Correct 1367 ms 66044 KB Output is correct
7 Correct 1099 ms 50104 KB Output is correct
8 Correct 1303 ms 66076 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15944 KB Output is correct
2 Correct 41 ms 15952 KB Output is correct
3 Correct 42 ms 15888 KB Output is correct
4 Correct 35 ms 15944 KB Output is correct
5 Incorrect 36 ms 15948 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 35 ms 15944 KB Output is correct
3 Correct 40 ms 15944 KB Output is correct
4 Correct 37 ms 15944 KB Output is correct
5 Incorrect 127 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 34 ms 15928 KB Output is correct
2 Correct 37 ms 15944 KB Output is correct
3 Correct 37 ms 15944 KB Output is correct
4 Incorrect 269 ms 38456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15928 KB Output is correct
2 Correct 37 ms 15944 KB Output is correct
3 Correct 37 ms 15944 KB Output is correct
4 Incorrect 269 ms 38456 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 37 ms 15960 KB Output is correct
3 Correct 192 ms 55836 KB Output is correct
4 Correct 1324 ms 65984 KB Output is correct
5 Correct 1089 ms 41140 KB Output is correct
6 Correct 1367 ms 66044 KB Output is correct
7 Correct 1099 ms 50104 KB Output is correct
8 Correct 1303 ms 66076 KB Output is correct
9 Correct 34 ms 15944 KB Output is correct
10 Correct 41 ms 15952 KB Output is correct
11 Correct 42 ms 15888 KB Output is correct
12 Correct 35 ms 15944 KB Output is correct
13 Incorrect 36 ms 15948 KB Output isn't correct
14 Halted 0 ms 0 KB -