Submission #566702

#	Time	Username	Problem	Language	Result	Execution time	Memory
566702		Ooops_sorry	Rainforest Jumps (APIO21_jumps)	C++14	56 / 100	4035 ms	36536 KiB

jumps

#include<bits/stdc++.h>
#ifndef LOCAL
    #include "jumps.h"
#endif

#define ld long double
#define ll long long
#define pb push_back

using namespace std;

const int INF = 1e9;

mt19937 rnd(51);

int n;
vector<int> h, l, r;
vector<vector<int>> po, po_r;

void init(int N, std::vector<int> H) {
    h = H;
    n = N;
    l.clear(), r.clear();
    l.resize(n, -1);
    r.resize(n, n);
    po.resize(20);
    po_r.resize(20);
    for (int i = 0; i < 20; i++) {
        po[i].resize(n);
        po_r[i].resize(n);
    }
    deque<int> q;
    for (int i = 0; i < n; i++) {
        while (q.size() > 0 && h[q.back()] < h[i]) {
            r[q.back()] = i;
            q.pop_back();
        }
        q.pb(i);
    }
    q.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (q.size() > 0 && h[q.back()] < h[i]) {
            l[q.back()] = i;
            q.pop_back();
        }
        q.pb(i);
    }
    for (int i = 0; i < n; i++) {
        int L = l[i], R = r[i];
        if (R == n) {
            po_r[0][i] = i;
        } else {
            po_r[0][i] = R;
        }
        if (L == -1) {
            if (R == n) {
                po[0][i] = i;
            } else {
                po[0][i] = R;
            }
        } else {
            if (R == n || h[L] > h[R]) {
                po[0][i] = L;
            } else {
                po[0][i] = R;
            }
        }
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            po[i][j] = po[i - 1][po[i - 1][j]];
            po_r[i][j] = po_r[i - 1][po_r[i - 1][j]];
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    int j = c, k = -1;
    for (int i = c; i <= d; i++) {
        if (h[i] > h[j]) {
            j = i;
        }
    }
    for (int i = b; i >= a && h[i] < h[j]; i--) {
        if (k == -1 || h[i] > h[k]) {
            k = i;
        }
    }
    if (k == -1) return -1;
    int cnt = 1;
    for (int i = 19; i >= 0; i--) {
        int ind = po[i][k];
        if (h[ind] < h[j] && r[ind] < c) {
            k = ind;
            cnt += (1 << i);
        }
    }
    if (r[k] >= c && r[k] <= d) {
        return cnt;
    }
    if (l[k] != -1 && h[l[k]] < h[j] && r[l[k]] >= c) {
        return cnt + 1;
    }
    for (int i = 19; i >= 0; i--) {
        int ind = po_r[i][k];
        if (r[ind] < c) {
            k = ind;
            cnt += (1 << i);
        }
    }
    k = r[k];
    if (r[k] > d) return -1;
    return cnt + 1;
}

#ifdef LOCAL

int my_solve(int a, int b, int c, int d) {
    map<int,int> dist;
    deque<int> q;
    for (int i = a; i <= b; i++) {
        dist[i] = 0;
        q.pb(i);
    }
    while (q.size() > 0) {
        int v = q.front();
        if (c <= v && v <= d) return dist[v];
        q.pop_front();
        int L = l[v], R = r[v];
        if (L != -1 && dist.find(L) == dist.end()) {
            dist[L] = dist[v] + 1;
            q.pb(L);
        }
        if (R != n && dist.find(R) == dist.end()) {
            dist[R] = dist[v] + 1;
            q.pb(R);
        }
    }
    return -1;
}

int main() {
  while (1) {
    int n = rnd() % 10 + 1, q = rnd() % 10 + 1;
    vector<int> h(n);
    iota(h.begin(), h.end(), 1);
    shuffle(h.begin(), h.end(), rnd);
    init(n, h);
    cout << n << endl;
    for (auto to : h) {
        cout << to << ' ';
    }
    cout << endl;
    for (int i = 0; i < q; i++) {
        vector<int> arr(4);
        for (int j = 0; j < 4; j++) arr[j] = rnd() % n;
        sort(arr.begin(), arr.end());
        if (arr[1] >= arr[2]) continue;
        cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << ' ' << arr[3] << endl;
        auto res = minimum_jumps(arr[0], arr[1], arr[2], arr[3]), res2 = my_solve(arr[0], arr[1], arr[2], arr[3]);
        if (res != res2) {
            cout << "BAD" << endl;
            cout << res << ' ' << res2 << endl;
            return 0;
        }
    }
  }
}

#endif

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19