제출 #1256887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256887		christhegamechanger	Obstacles for a Llama (IOI25_obstacles)	C++17	24 / 100	278 ms	14916 KiB

obstacles

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

namespace Obstacles {

struct SegTree {
    int n;
    vector<int> mn, mx;
    void build(const vector<int>& a, int id, int l, int r) {
        if (l == r) { mn[id] = mx[id] = a[l]; return; }
        int m = (l + r) >> 1;
        build(a, id<<1, l, m);
        build(a, id<<1|1, m+1, r);
        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(a, 1, 0, n-1);
    }
    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 { return (l>r) ? INT_MAX : 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);
        if (left != -1) return left;
        return first_ge(id<<1|1, m+1, r, ql, qr, t);
    }
    int first_ge(int l, int r, int t) const { return (l>r) ? -1 : 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);
        if (right != -1) return right;
        return last_ge(id<<1, l, m, ql, qr, t);
    }
    int last_ge(int l, int r, int t) const { return (l>r) ? -1 : last_ge(1,0,n-1,l,r,t); }
};

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

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;
}

inline pair<int,int> component_bounds(int L, int R, int S, int t) {
    // contiguous block around S inside [L,R] with H < t
    int left_bar  = segH.last_ge(L, S, t);
    int right_bar = segH.first_ge(S, R, t);
    int Lb = max(L, left_bar + 1);
    int Rb = min(R, (right_bar == -1 ? R : right_bar - 1));
    return {Lb, Rb};
}

} // namespace Obstacles

using Obstacles::Trow; using Obstacles::Hcol;
using Obstacles::prefMinT; using Obstacles::prefMaxT;
using Obstacles::segH; using Obstacles::component_bounds;
using Obstacles::last_r_with_prefMin_gt;
using Obstacles::N; using Obstacles::M;

void initialize(vector<int> T, vector<int> H) {
    Trow = move(T); Hcol = move(H);
    N = (int)Trow.size(); M = (int)Hcol.size();
    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]);
        }
    }
    segH.init(Hcol);
}

bool can_reach(int L, int R, int S, int D) {
    // Bài đảm bảo (0,S) và (0,D) đều hợp lệ; check an toàn:
    if (!(Trow[0] > Hcol[S])) return false;

    // Hàng sâu nhất mà vẫn leo ngược trên cột D về 0 được
    int rD = last_r_with_prefMin_gt(Hcol[D]);
    if (rD < 0) return false;

    int tcur = Trow[0];
    auto seg = component_bounds(L, R, S, tcur);
    int Lb = seg.first, Rb = seg.second;

    if (Lb <= Rb && D >= Lb && D <= Rb) return true;

    while (true) {
        if (Lb > Rb) return false; // đoạn rỗng

        int hmin = segH.qmin(Lb, Rb);
        int rmax = last_r_with_prefMin_gt(hmin);
        if (rmax < 0) return false;

        // Chỉ dùng các hàng không sâu hơn rD để vẫn leo được trên cột D
        int rAllowed = min(rmax, rD);
        int tnew = prefMaxT[rAllowed];

        if (tnew <= tcur) return false; // không mở rộng thêm được
        tcur = tnew;

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

        if (D >= Lb && D <= Rb) return true;
    }
}

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