Submission #566704

#	Time	Username	Problem	Language	Result	Execution time	Memory
566704		Ooops_sorry	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1836 ms	85088 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, N = 2e5 + 10;

mt19937 rnd(51);

int n;
vector<int> h, l, r, ind(N);
vector<vector<int>> po, po_r;
vector<int> t[4 * N];

struct SegTree {
    vector<int> t;
    int n;
    void build(int n_) {
        n = n_;
        t.resize(2 * n);
    }
    void upd(int i, int val) {
        i += n;
        t[i] = val;
        for (; i > 1; i /= 2) {
            t[i / 2] = max(t[i], t[i ^ 1]);
        }
    }
    int get(int l, int r) {
        l += n, r += n + 1;
        int ans = -1;
        while (l < r) {
            if (l & 1) {
                ans = max(ans, t[l++]);
            }
            if (r & 1) {
                ans = max(ans, t[--r]);
            }
            l /= 2, r /= 2;
        }
        return ans;
    }
} T;

void upd(int v) {
    for (auto to : t[2 * v]) {
        t[v].pb(to);
    }
    for (auto to : t[2 * v + 1]) {
        t[v].pb(to);
    }
    sort(t[v].begin(), t[v].end());
}

void build(int v, int l, int r) {
    t[v].clear();
    if (l == r) {
        t[v].pb(h[l]);
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m), build(2 * v + 1, m + 1, r);
    upd(v);
}

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;
    T.build(n);
    for (int i = 0; i < n; i++) {
        ind[h[i]] = i;
        T.upd(i, h[i]);
    }
    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]];
        }
    }
    build(1, 0, n - 1);
}

int get_max(int v, int tl, int tr, int l, int r, int mx) {
    if (l > r) return -1;
    if (tl == l && tr == r) {
        if (mx == INF) {
            return t[v].back();
        } else {
            int l = -1, r = t[v].size();
            while (r - l > 1) {
                int mid = (r + l) / 2;
                if (t[v][mid] < mx) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            if (l == -1) return -1;
            else return t[v][l];
        }
    }
    int tm = (tl + tr) / 2;
    int i = get_max(2 * v, tl, tm, l, min(r, tm), mx), j = get_max(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, mx);
    return max(i, j);
}

int minimum_jumps(int a, int b, int c, int d) {
    int j = ind[get_max(1, 0, n - 1, c, d, INF)];
    int L = a - 1, R = b + 1;
    while (R - L > 1) {
        int mid = (R + L) / 2;
        if (T.get(mid, b) < h[j]) {
            R = mid;
        } else {
            L = mid;
        }
    }
    int k = get_max(1, 0, n - 1, R, b, h[j]);
    if (k == -1) return -1;
    k = ind[k];
    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: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19