oj.uz

Submission #478174

# Submission time Handle Problem Language Result Execution time Memory
478174 2021-10-06T07:44:43 Z khoabright Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 1 ms 200 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;

int L[N], R[N], h[N];
int my_size;

void cal_LR() {
    rep(i, 1, my_size) {
        rep1(j, i - 1, 1) if (h[j] > h[i]) {
            L[i] = j;
            break;
        } 
        rep(j, i + 1, my_size) if (h[j] > h[i]) {
            R[i] = j;
            break;
        }
    }
}

int minimum_jumps(int a, int b, int c, int 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];
        if (!vst[v]) {
            q.push({v, w + 1});
            vst[v] = 1;
        }
        v = R[u];
        if (!vst[v]) {
            q.push({v, w + 1});
            vst[v] = 1;
        }
    }

    return -1;
}

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;
//     // int array[10];
//     // rep(i, 1, x) cin >> array[i - 1];
//     // init(x,array);
    
//     // rep(i, 1, my_size) cout << h[i] << ' ';
//     // cout << '\my_size';
//     // rep(i, 1, my_size) cout << L[i] << ' ' << R[i]<< '\my_size';

//     // int q; cin >> q;
//     // while (q--) {
//     //     int A, B, C, D;
//     //     cin >> A >> B >> C >> D;
//     //     cout << minimum_jumps(A + 1, B + 1, C + 1, D + 1) << '\my_size';
//     // }
// }

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -