Submission #1125394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125394		SamueleVid	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	1104 ms	71912 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int N;
vector<int> H;

constexpr ll PW = 262144;
constexpr ll LOG = 20;

struct segment {
    vector<ll> seg;
    segment() {
        seg.assign(2 * PW, 1e9);
    }

    void update(int x, ll d) {
        x += PW;
        seg[x] = d;
        x /= 2;
        while (x >= 1) {
            seg[x] = min(seg[2 * x], seg[2 * x + 1]);
            x /= 2;
        }
    }

    ll query(int l, int r) {
        l += PW; r += PW;
        ll sol = 1e9;
        while (l <= r) {
            if (l % 2 == 1) {
                sol = min(sol, seg[l]);
                l ++;
            }
            if (r % 2 == 0) {
                sol = min(sol, seg[r]);
                r --;
            }
            l /= 2; r /= 2;
        }
        return sol;
    }

    void clear() {
        for (int i = 0; i < 2 * PW; i ++) seg[i] = 1e9;
    }
};

struct binlift {
    int N, LOG;
    vector<int> p;
    vector<int> depth;
    vector<vector<int>> bl;
    vector<vector<int>> adj;
    
    binlift() {}
    binlift(int N_, int LOG_, vector<int> p_) {
        N = N_;
        LOG = LOG_;
        p = p_;
        depth.resize(N);
        bl.assign(LOG_, vector<int>(N));
        adj.resize(N);
        for (int i = 0; i < N; i ++) {
            if (p[i] != -1) adj[p[i]].push_back(i);
        }

        for (int i = 0; i < N; i ++) {
            if (p[i] == -1) {
                depth[i] = 0;
                dfs_depth(i);
            }
        }

        for (int i = 0; i < N; i ++) {
            bl[0][i] = (p[i] != -1) ? p[i] : i;
        }

        for (int p = 1; p < LOG; p ++) {
            for (int i = 0; i < N; i ++) {
                bl[p][i] = bl[p - 1][bl[p - 1][i]];
            }
        }      

        // for (int p = 0; p < LOG; p ++) {
        //     cout << "p : " << p << " -> ";
        //     for (int i = 0; i < N; i ++) cout << bl[p][i] << " ";
        //     cout << '\n';
        // }  
    }

    void dfs_depth(int u) {
        for (auto x : adj[u]) {
            depth[x] = depth[u] + 1;
            dfs_depth(x);
        }
    }

    int n_th_ancestor(int u, int n) {
        // cout << "n, u : " << n << " " << u << '\n';
        for (int i = LOG - 1; i >= 0; i --) {
            if (n & (1 << i)) {
                // cout << "2 ^ " << i << " esimo parent di " << u << '\n';
                u = bl[i][u];
            }
            // cout << "-> " << u << '\n';
        }
        return u;
    }
};

segment seg;

vector<int> p_max;
vector<int> p_dx;

binlift bl_max, bl_dx;

void init(int N, vector<int> H) {
    ::N = N;
    ::H = H;

    vector<int> inv_H(N + 1);
    for (int i = 0; i < N; i ++) inv_H[H[i]] = i;

    p_max.assign(N, -1);
    p_dx.assign(N, -1);

    // a destra
    for (int i = N - 1; i >= 0; i --) {
        int u = seg.query(H[i] + 1, N);
        if (u != 1e9) {
            p_dx[i] = u;
            p_max[i] = u;
        }
        seg.update(H[i], i);
    }

    seg.clear();
    // a sinistra
    for (int i = 0; i < N; i ++) {
        int u = -seg.query(H[i] + 1, N);
        if (u != -1e9)  {
            if (p_max[i] != -1 && H[u] > H[p_max[i]]) p_max[i] = u; 
        }
        seg.update(H[i], -i);
    }

    bl_max = binlift(N, LOG, p_max);
    bl_dx = binlift(N, LOG, p_dx);
}

int minimum_jumps(int A, int B, int C, int D) {
    // A == B e C == D

    // cout << "a, c : " << A << " " << C << '\n';

    int k = -1;
    for (int p = PW; p >= 1; p /= 2) {
        // cout << "k, p, k + p : " << k << " " << p << " " << k + p << '\n';
        int u = bl_max.n_th_ancestor(A, (p + k));
        if (bl_dx.depth[C] > bl_dx.depth[u]) continue;
        int v = bl_dx.n_th_ancestor(u, bl_dx.depth[u] - bl_dx.depth[C]);
        if (v == C) k += p;
    }

    if (k == -1) return -1;

    int u = bl_max.n_th_ancestor(A, k);

    int sol = (bl_dx.depth[u] - bl_dx.depth[C]) + (bl_max.depth[A] - bl_max.depth[u]);
    return sol;

}

// int main() {
//     int N, Q;
//     cin >> N >> Q;

//     vector<int> H(N);
//     for(int &x: H) cin >> x;
//     init(N, H);

//     for(int i=0; i<Q; i++){
//         int A, B, C, D;
//         cin >> A >> B >> C >> D;

//         cout << minimum_jumps(A, B, C, D) << "\n";
//     }
// }

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