Submission #1274818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274818		mehrzad	Obstacles for a Llama (IOI25_obstacles)	C++20	21 / 100	2097 ms	14420 KiB

obstacles

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

struct SegTree {
    struct Node {
        int mx;          // maximum H in the segment
        int mn;          // minimum H in the segment
        int mnPos;       // position of the minimum (any)
    };
    int n;
    vector<Node> st;
    vector<int> *arrPtr; // pointer to original H array

    SegTree() : n(0), arrPtr(nullptr) {}

    void init(const vector<int> &arr) {
        n = (int)arr.size();
        arrPtr = const_cast<vector<int>*>(&arr);
        st.assign(4 * n, Node());
        build(1, 0, n - 1);
    }

    void build(int p, int l, int r) {
        if (l == r) {
            int val = (*arrPtr)[l];
            st[p] = {val, val, l};
            return;
        }
        int m = (l + r) >> 1;
        build(p << 1, l, m);
        build(p << 1 | 1, m + 1, r);
        pull(p);
    }

    void pull(int p) {
        const Node &L = st[p << 1];
        const Node &R = st[p << 1 | 1];
        st[p].mx = max(L.mx, R.mx);
        if (L.mn <= R.mn) {
            st[p].mn = L.mn;
            st[p].mnPos = L.mnPos;
        } else {
            st[p].mn = R.mn;
            st[p].mnPos = R.mnPos;
        }
    }

    // range minimum query (value, position)
    pair<int,int> queryMin(int p, int l, int r, int ql, int qr) const {
        if (qr < l || ql > r) return {INT_MAX, -1};
        if (ql <= l && r <= qr) return {st[p].mn, st[p].mnPos};
        int m = (l + r) >> 1;
        auto left = queryMin(p<<1, l, m, ql, qr);
        auto right = queryMin(p<<1|1, m+1, r, ql, qr);
        if (left.first <= right.first) return left;
        return right;
    }

    // public wrapper
    pair<int,int> rangeMin(int l, int r) const {
        return queryMin(1, 0, n-1, l, r);
    }

    // find first index in [ql,qr] where H >= thr, returns n if none
    int findFirstGE(int p, int l, int r, int ql, int qr, int thr) const {
        if (qr < l || ql > r) return n;
        if (st[p].mx < thr) return n;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int leftRes = findFirstGE(p<<1, l, m, ql, qr, thr);
        if (leftRes != n) return leftRes;
        return findFirstGE(p<<1|1, m+1, r, ql, qr, thr);
    }

    // find last index in [ql,qr] where H >= thr, returns -1 if none
    int findLastGE(int p, int l, int r, int ql, int qr, int thr) const {
        if (qr < l || ql > r) return -1;
        if (st[p].mx < thr) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int rightRes = findLastGE(p<<1|1, m+1, r, ql, qr, thr);
        if (rightRes != -1) return rightRes;
        return findLastGE(p<<1, l, m, ql, qr, thr);
    }

    // wrappers
    int firstGE(int l, int r, int thr) const {
        if (l > r) return n;
        return findFirstGE(1, 0, n-1, l, r, thr);
    }
    int lastGE(int l, int r, int thr) const {
        if (l > r) return -1;
        return findLastGE(1, 0, n-1, l, r, thr);
    }
};

static vector<int> T_global;
static vector<int> H_global;
static vector<int> prefMaxT;
static SegTree seg;
static int N, M;

// compute deepest reachable row index starting from a given column position
static int computeDepth(int startPos) {
    int curPos = startPos;
    int curMin = H_global[curPos];
    int depth = 0;                 // row 0 is always reachable
    for (int i = 1; i < N; ++i) {
        if (T_global[i] <= curMin) break;   // cannot go down to this row
        // expand the horizontal interval on row i starting from curPos
        int leftBound = 0;
        if (curPos > 0) {
            int leftBlock = seg.lastGE(0, curPos - 1, T_global[i]);
            if (leftBlock != -1) leftBound = leftBlock + 1;
        }
        int rightBound = M - 1;
        if (curPos < M - 1) {
            int rightBlock = seg.firstGE(curPos + 1, M - 1, T_global[i]);
            if (rightBlock != M) rightBound = rightBlock - 1;
        }
        // query the minimum humidity inside the new interval
        auto minInfo = seg.rangeMin(leftBound, rightBound);
        curPos = minInfo.second;
        curMin = minInfo.first;
        depth = i;
    }
    return depth;
}

void initialize(vector<int> T, vector<int> H) {
    T_global.swap(T);
    H_global.swap(H);
    N = (int)T_global.size();
    M = (int)H_global.size();

    prefMaxT.resize(N);
    for (int i = 0; i < N; ++i) {
        prefMaxT[i] = (i == 0) ? T_global[0] : max(prefMaxT[i-1], T_global[i]);
    }
    seg.init(H_global);
}

bool can_reach(int L, int R, int S, int D) {
    // According to the sub‑task constraints L == 0 and R == M-1, so we ignore them.
    if (S == D) return true;

    // ------- max humidity on the whole column interval [min(S,D), max(S,D)] -------
    int leftIdx = min(S, D);
    int rightIdx = max(S, D);
    int maxH = -1;
    for (int i = leftIdx; i <= rightIdx; ++i) {
        if (H_global[i] > maxH) maxH = H_global[i];
    }

    // ------- start interval on row 0 (containing S) -------
    int Ls = S;
    while (Ls > 0 && H_global[Ls - 1] < T_global[0]) --Ls;
    int Rs = S;
    while (Rs + 1 < M && H_global[Rs + 1] < T_global[0]) ++Rs;
    auto startInfo = seg.rangeMin(Ls, Rs);
    int startPos = startInfo.second;
    int depthStart = computeDepth(startPos);

    // ------- target interval on row 0 (containing D) -------
    int Ld = D;
    while (Ld > 0 && H_global[Ld - 1] < T_global[0]) --Ld;
    int Rd = D;
    while (Rd + 1 < M && H_global[Rd + 1] < T_global[0]) ++Rd;
    auto targetInfo = seg.rangeMin(Ld, Rd);
    int targetPos = targetInfo.second;
    int depthTarget = computeDepth(targetPos);

    int reachableDepth = min(depthStart, depthTarget);
    int maxReachableTemp = prefMaxT[reachableDepth];

    return maxReachableTemp > maxH;
}

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