Submission #1273668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273668		lucas110550	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	185 ms	20352 KiB

obstacles

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

// ---------- DSU ----------
struct DSU {
        vector<int> p, sz;
        DSU(int n = 0) { init(n); }
        void init(int n) {
                p.resize(n);
                sz.assign(n, 1);
                iota(p.begin(), p.end(), 0);
        }
        int find(int x) {
                return p[x] == x ? x : p[x] = find(p[x]);
        }
        void unite(int a, int b) {
                a = find(a);
                b = find(b);
                if (a == b) return;
                if (sz[a] < sz[b]) swap(a, b);
                p[b] = a;
                sz[a] += sz[b];
        }
};

// ---------- Segment Tree for range maximum ----------
struct SegTree {
        int n;
        vector<int> seg;
        SegTree() {}
        explicit SegTree(const vector<int>& a) { build(a); }
        void build(const vector<int>& a) {
                n = (int)a.size();
                seg.assign(4 * n, 0);
                build(1, 0, n - 1, a);
        }
        void build(int node, int l, int r, const vector<int>& a) {
                if (l == r) {
                        seg[node] = a[l];
                        return;
                }
                int mid = (l + r) >> 1;
                build(node << 1, l, mid, a);
                build(node << 1 | 1, mid + 1, r, a);
                seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
        }
        int query(int L, int R) const { return query(1, 0, n - 1, L, R); }
        int query(int node, int l, int r, int L, int R) const {
                if (R < l || r < L) return INT_MIN;
                if (L <= l && r <= R) return seg[node];
                int mid = (l + r) >> 1;
                return max(query(node << 1, l, mid, L, R),
                                   query(node << 1 | 1, mid + 1, r, L, R));
        }
};

// ---------- Global data ----------
vector<int> T, H;
vector<int> depth;                // max continuous prefix where column stays free
vector<int> col2int;            // column -> interval id (or -1)
vector<int> prefMaxT;      // prefix maximum of T
struct Interval {
        int left, right;
        int maxDepth;   // max depth among its columns
        int Tval;          // prefixMaxT[maxDepth]
        int id;
};
vector<Interval> intervals;
DSU dsu;
SegTree seg;

// ---------- Helper to compute depth ----------
void computeDepth() {
        int N = T.size(), M = H.size();
        depth.assign(M, N - 1);
        // rows sorted by temperature (value, index)
        vector<pair<int, int>> rows;
        rows.reserve(N);
        for (int i = 0; i < N; ++i) rows.emplace_back(T[i], i);
        sort(rows.begin(), rows.end());                         // ascending by temperature

        // columns sorted by humidity
        vector<int> colIdx(M);
        iota(colIdx.begin(), colIdx.end(), 0);
        sort(colIdx.begin(), colIdx.end(),
                 [&](int a, int b) { return H[a] < H[b]; });

        const int INF = INT_MAX;
        int rp = 0;
        int curMin = INF;
        for (int idx : colIdx) {
                while (rp < N && rows[rp].first <= H[idx]) {
                        curMin = min(curMin, rows[rp].second);
                        ++rp;
                }
                if (curMin == INF) depth[idx] = N - 1;
                else depth[idx] = curMin - 1;
        }
}

// ---------- Helper to build intervals on row 0 ----------
void buildIntervals() {
        int M = H.size();
        intervals.clear();
        col2int.assign(M, -1);
        int i = 0;
        while (i < M) {
                if (T[0] > H[i]) {
                        int start = i;
                        int maxH = H[i];
                        int maxDepth = depth[i];
                        ++i;
                        while (i < M && T[0] > H[i]) {
                                maxH = max(maxH, H[i]);
                                maxDepth = max(maxDepth, depth[i]);
                                ++i;
                        }
                        Interval it;
                        it.left = start;
                        it.right = i - 1;
                        it.maxDepth = maxDepth;
                        it.Tval = 0; // will be set later after prefixMaxT known
                        it.id = intervals.size();
                        intervals.push_back(it);
                        int id = it.id;
                        for (int j = start; j <= i - 1; ++j) col2int[j] = id;
                } else {
                        ++i;
                }
        }
        int K = intervals.size();
        for (int id = 0; id < K; ++id) {
                intervals[id].Tval = prefMaxT[intervals[id].maxDepth];
        }
}

// ---------- Main initialization ----------
void initialize(vector<int> T_, vector<int> H_) {
        T.swap(T_);
        H.swap(H_);
        int N = T.size();
        int M = H.size();

        // prefix maximum of temperatures
        prefMaxT.assign(N, 0);
        prefMaxT[0] = T[0];
        for (int i = 1; i < N; ++i) prefMaxT[i] = max(prefMaxT[i - 1], T[i]);

        // compute depth for each column
        computeDepth();

        // build intervals on the first row
        buildIntervals();

        // initialise DSU and segment tree
        int K = intervals.size();
        dsu.init(K);
        seg = SegTree(H);

        // sort interval ids by decreasing Tval (break ties by left coordinate)
        vector<int> order(K);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(),
                 [&](int a, int b) {
                         if (intervals[a].Tval != intervals[b].Tval)
                                 return intervals[a].Tval > intervals[b].Tval;
                         return intervals[a].left < intervals[b].left;
                 });

        // active set ordered by left endpoint
        set<pair<int, int>> active; // (left, interval id)

        for (int idx : order) {
                const Interval &cur = intervals[idx];
                int curT = cur.Tval;

                // locate where this interval would be inserted
                auto itSucc = active.lower_bound({cur.left, -1});

                // predecessor (the greatest left < cur.left)
                if (itSucc != active.begin()) {
                        auto itPrev = prev(itSucc);
                        int pid = itPrev->second;
                        const Interval &p = intervals[pid];
                        int regionMax = seg.query(p.left, cur.right);
                        if (regionMax < curT) dsu.unite(pid, idx);
                }

                // successor (the smallest left >= cur.left)
                if (itSucc != active.end()) {
                        int sid = itSucc->second;
                        const Interval &s = intervals[sid];
                        int regionMax = seg.query(cur.left, s.right);
                        if (regionMax < curT) dsu.unite(idx, sid);
                }

                active.insert({cur.left, idx});
        }
}

// ---------- Query ----------
bool can_reach(int L, int R, int S, int D) {
        // For the sub‑problem L=0,R=M-1, we can ignore L,R.
        int idS = col2int[S];
        int idD = col2int[D];
        if (idS == -1 || idD == -1) return false; // should not happen for valid queries
        if (idS == idD) return true;
        return dsu.find(idS) == dsu.find(idD);
}

• 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: 0 / 17