Submission #1258732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258732		christhegamechanger	Obstacles for a Llama (IOI25_obstacles)	C++17	37 / 100	349 ms	14828 KiB

obstacles

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

namespace Solver {

    int N, M;
    vector<int> Trow, Hcol;
    vector<int> prefMinT, prefMaxT;

    struct SegTree {
        int n;
        vector<int> mn, mx; // mn = min(H), mx = max(H) for pruning GE-queries

        void build(int id, int l, int r, const vector<int>& a) {
            if (l == r) { mn[id] = mx[id] = a[l]; return; }
            int m = (l + r) >> 1;
            build(id<<1, l, m, a);
            build(id<<1|1, m+1, r, a);
            mn[id] = min(mn[id<<1], mn[id<<1|1]);
            mx[id] = max(mx[id<<1], mx[id<<1|1]);
        }
        void init(const vector<int>& a) {
            n = (int)a.size();
            mn.assign(4*n, INT_MAX);
            mx.assign(4*n, INT_MIN);
            if (n) build(1, 0, n-1, a);
        }
        int qmin(int id, int l, int r, int ql, int qr) const {
            if (qr < l || r < ql) return INT_MAX;
            if (ql <= l && r <= qr) return mn[id];
            int m = (l + r) >> 1;
            return min(qmin(id<<1, l, m, ql, qr), qmin(id<<1|1, m+1, r, ql, qr));
        }
        int qmin(int l, int r) const {
            if (l > r) return INT_MAX;        // guard: never crash on empty
            return qmin(1, 0, n-1, l, r);
        }
        int first_ge(int id, int l, int r, int ql, int qr, int t) const {
            if (qr < l || r < ql || mx[id] < t) return -1;
            if (l == r) return l;
            int m = (l + r) >> 1;
            int left = first_ge(id<<1, l, m, ql, qr, t);
            return (left != -1) ? left : first_ge(id<<1|1, m+1, r, ql, qr, t);
        }
        int first_ge(int l, int r, int t) const {
            if (l > r) return -1;
            return first_ge(1, 0, n-1, l, r, t);
        }
        int last_ge(int id, int l, int r, int ql, int qr, int t) const {
            if (qr < l || r < ql || mx[id] < t) return -1;
            if (l == r) return l;
            int m = (l + r) >> 1;
            int right = last_ge(id<<1|1, m+1, r, ql, qr, t);
            return (right != -1) ? right : last_ge(id<<1, l, m, ql, qr, t);
        }
        int last_ge(int l, int r, int t) const {
            if (l > r) return -1;
            return last_ge(1, 0, n-1, l, r, t);
        }
    } segH;

    // largest r such that prefMinT[r] > h; -1 if none
    inline int last_r_with_prefMin_gt(int h) {
        int lo = 0, hi = N - 1, ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (prefMinT[mid] > h) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }

    // maximal contiguous block around S inside [L,R] with H < t
    inline pair<int,int> component_bounds(int L, int R, int S, int t) {
        // Satisfies H[S] < t in all our calls; dải này luôn chứa S
        int left_bar  = segH.last_ge(L, S, t);         // last index with H >= t in [L..S]
        int right_bar = segH.first_ge(S, R, t);        // first index with H >= t in [S..R]
        int Lb = max(L, left_bar + 1);
        int Rb = min(R, (right_bar == -1 ? R : right_bar - 1));
        return {Lb, Rb};
    }

    void initialize(vector<int> T, vector<int> H) {
        Trow = move(T); Hcol = move(H);
        N = (int)Trow.size(); M = (int)Hcol.size();

        // prefix min/max of T
        prefMinT.assign(N, 0);
        prefMaxT.assign(N, 0);
        for (int i = 0; i < N; ++i) {
            if (i == 0) prefMinT[i] = prefMaxT[i] = Trow[i];
            else {
                prefMinT[i] = min(prefMinT[i-1], Trow[i]);
                prefMaxT[i] = max(prefMaxT[i-1], Trow[i]);
            }
        }
        // segtree on H
        segH.init(Hcol);
    }

    bool can_reach(int L, int R, int S, int D) {
        // Đề đảm bảo (0,S),(0,D) hợp lệ; kiểm tra an toàn để khỏi RE
        if (!(Trow[0] > Hcol[S] && Trow[0] > Hcol[D])) return false;

        // Dải hàng-0 của D với t = T[0]; dùng để tính "độ sâu trần"
        auto dseg = component_bounds(L, R, D, Trow[0]);
        int DL = dseg.first, DR = dseg.second;
        if (DL > DR) return false; // guard; thực tế D luôn nằm trong dải

        int hD   = segH.qmin(DL, DR);
        int rCap = last_r_with_prefMin_gt(hD);  // sâu tối đa vẫn ngoi lên trong dải của D
        if (rCap < 0) return false;             // cũng chỉ là guard

        // Dải hiện tại quanh S với tcur
        int tcur = Trow[0];
        auto sseg = component_bounds(L, R, S, tcur);
        int Lb = sseg.first, Rb = sseg.second;

        // Nếu đã chạm dải hàng-0 của D ⇒ có đường đi
        if (max(Lb, DL) <= min(Rb, DR)) return true;

        // Mở rộng bằng "thang máy" tốt nhất; số vòng ≤ 11 (miền giá trị 0..10)
        for (int iter = 0; iter < 20; ++iter) { // 20 = guard
            if (Lb > Rb) return false;          // luôn chặn trước khi qmin
            
            int hmin = segH.qmin(Lb, Rb);
            int rmax = last_r_with_prefMin_gt(hmin);
            if (rmax < 0) return false;

            int rAllowed = min(rmax, rCap);
            int tnew     = prefMaxT[rAllowed];
            if (tnew <= tcur) return false;     // không nới thêm được

            tcur = tnew;
            sseg = component_bounds(L, R, S, tcur);
            Lb = sseg.first; Rb = sseg.second;

            if (max(Lb, DL) <= min(Rb, DR)) return true;
        }
        return false; // guard
    }
} // namespace Solver

// ----- required interface -----
void initialize(std::vector<int> T, std::vector<int> H) { Solver::initialize(move(T), move(H)); }
bool can_reach(int L, int R, int S, int D) { return Solver::can_reach(L, R, S, D); }

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