Submission #1256516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256516		biank	Obstacles for a Llama (IOI25_obstacles)	C++20	100 / 100	516 ms	116628 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

struct DSU {
    vi par, mini, maxi, tim;
    vector<ii> edges;
    DSU(int n) : par(n), mini(n), maxi(n), tim(n, 0) {
        iota(all(par), 0);
        mini = maxi = par;
    }
    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    bool unite(int x, int y, int t) {
        x = find(x), y = find(y);
        if (x == y) return false;
        int p = sz(par);
        par[x] = p, par[y] = p;
        par.pb(p);
        mini.pb(min(mini[x], mini[y]));
        maxi.pb(max(maxi[x], maxi[y]));
        tim.pb(t);
        edges.eb(p, x);
        edges.eb(p, y);
        return true;
    }
};

const int INF = 1e9;

struct SegTree {
    int n;
    vi st;
    SegTree(vi &v) {
        n = 1; while (n < sz(v)) n *= 2;
        st.assign(2 * n, INF);
        forn(i, sz(v)) st[i + n] = v[i];
        dforsn(i, 1, n) st[i] = min(st[2 * i], st[2 * i + 1]);
    }
    int query(int l, int r) {
        int ret = INF;
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) ret = min(ret, st[l++]);
            if (r & 1) ret = min(st[--r], ret);
        }
        return ret;
    }
    int find(int s, int e, int k, tuple<int, int, int> node, bool t) {
        auto [l, r, u] = node;
        if (e <= l || r <= s || st[u] >= k) return -1;
        if (r - l == 1) return l;
        int m = (l + r) / 2;
        tuple<int, int, int> a = {l, m, 2 * u}, b = {m, r, 2 * u + 1};
        if (t) swap(a, b);
        int ret = find(s, e, k, a, t);
        if (ret != -1) return ret;
        return find(s, e, k, b, t);
    }
    int find(int s, int e, int k, bool t) {
        return find(s, e, k, {0, n, 1}, t);
    }
};

const int MAX_N = 4e5 + 9;
const int MAX_K = 20;

int par[MAX_K][MAX_N];
int mini[MAX_K][MAX_N];
int maxi[MAX_K][MAX_N];
int depth[MAX_N];

void initialize(vi T, vi H) {
    const int n = sz(T), m = sz(H);
    vector<bool> active(m, false);
    DSU dsu(m);
    vi order(m);
    iota(all(order), 0);
    sort(all(order), [&](const int &lhs, const int &rhs) {
        return H[lhs] < H[rhs];
    });
    auto activate = [&](int i, int t) {
        if (i > 0 && active[i - 1]) dsu.unite(i - 1, i, t);
        if (i + 1 < m && active[i + 1]) dsu.unite(i, i + 1, t);
        active[i] = true;
    };
    {
        int maxT = -INF, j = 0;
        forn(i, n) if (T[i] > maxT) {
            maxT = T[i];
            while (j < m && H[order[j]] < T[i]) {
                activate(order[j++], i);
            }
        }
    }
    const int N = sz(dsu.par);
    SegTree t(T), h(H);
    reverse(all(dsu.edges));
    forn(u, N) {
        par[0][u] = u;
        mini[0][u] = m - 1;
        maxi[0][u] = 0;
    }
    for (auto [p, u] : dsu.edges) {
        int j = dsu.tim[p], i = dsu.tim[u];
        if (i == j) {
            par[0][u] = p;
            depth[u] = depth[p] + 1;
            
            continue;
        }
        int l = dsu.mini[u], r = dsu.maxi[u];
        int k = t.query(i, j);
        int first = h.find(l, r + 1, k, 0), last = h.find(l, r + 1, k, 1);
        if (first != -1) {
            assert(last != -1);
            par[0][u] = p;
            depth[u] = depth[p] + 1;
            mini[0][u] = last;
            maxi[0][u] = first;
        }
    }
    forn(i, MAX_K - 1) forn(u, N) {
        int v = par[i][u];
        par[i + 1][u] = par[i][v];
        mini[i + 1][u] = min(mini[i][u], mini[i][v]);
        maxi[i + 1][u] = max(maxi[i][u], maxi[i][v]);
    }
}

ii query(int u, int v) {
    int l = u, r = v;
    if (depth[u] > depth[v]) {
        int diff = depth[u] - depth[v];
        forn(i, MAX_K) if (diff >> i & 1) {
            l = min(l, mini[i][u]);
            u = par[i][u];
        }
    }
    if (depth[v] > depth[u]) {
        int diff = depth[v] - depth[u];
        forn(i, MAX_K) if (diff >> i & 1) {
            r = max(r, maxi[i][v]);
            v = par[i][v];
        }
    }
    if (u == v) return {l, r};
    dforn(i, MAX_K) if (par[i][u] != par[i][v]) {
        l = min(l, mini[i][u]), r = max(r, maxi[i][v]);
        u = par[i][u], v = par[i][v];
    }
    l = min(l, mini[0][u]), r = max(r, maxi[0][v]);
    u = par[0][u], v = par[0][v];
    if (u != v) return {-1, -1};
    return {l, r};
}

bool can_reach(int L, int R, int S, int D) {
    if (S > D) swap(S, D);
    auto [l, r] = query(S, D);
    return L <= l && r <= R;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 21 / 21
• Subtask 5: 25 / 25
• Subtask 6: 17 / 17