Submission #1258744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258744		christhegamechanger	Obstacles for a Llama (IOI25_obstacles)	C++17	23 / 100	85 ms	41272 KiB

obstacles

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

namespace Obstacles {

static const int MAXV = 11; // vì T,H ∈ [0..10]

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

// prefix min/max của T
vector<int> prefMinT, prefMaxT;

// lastGreater[h] = chỉ số r lớn nhất sao cho prefMinT[r] > h (h=0..10), -1 nếu không có
int lastGreater[MAXV];

// Sparse Table cho RMQ min(H)
vector<int> lg2;
vector<vector<int>> st; // st[k][i] = min trên [i, i+2^k-1]

// Với mỗi ngưỡng t (0..10): rào trái/phải gần nhất có H >= t
vector<vector<int>> prevGE, nextGE; // [11][M]

// --- RMQ min trên H ---
inline int rmqMinH(int l, int r) {
    if (l > r) return INT_MAX;
    int len = r - l + 1, k = lg2[len];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

// --- Dải cột quanh X trong [L,R] với điều kiện H < t ---
inline pair<int,int> span_around(int L, int R, int X, int t) {
    // rào trái = prevGE[t][X], rào phải = nextGE[t][X]
    int Lbar = prevGE[t][X];
    int Rbar = nextGE[t][X];
    int Lb = max(L, Lbar + 1);
    int Rb = min(R, (Rbar == M ? R : Rbar - 1));
    return {Lb, Rb};
}

} // namespace Obstacles

using namespace Obstacles;

// ----------------- initialize -----------------
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 của 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]);
        }
    }

    // lastGreater[h] cho h=0..10
    for (int h = 0; h < MAXV; ++h) lastGreater[h] = -1;
    for (int r = 0; r < N; ++r) {
        int upTo = min(prefMinT[r] - 1, MAXV - 1); // mọi h <= prefMinT[r]-1 đều thỏa
        for (int h = 0; h <= upTo; ++h) lastGreater[h] = r;
    }

    // Sparse Table trên H (min)
    lg2.assign(M + 1, 0);
    for (int i = 2; i <= M; ++i) lg2[i] = lg2[i >> 1] + 1;
    int K = lg2[M];
    st.assign(K + 1, vector<int>(M));
    for (int j = 0; j < M; ++j) st[0][j] = Hcol[j];
    for (int k = 1; k <= K; ++k) {
        int half = 1 << (k - 1);
        for (int j = 0; j + (1 << k) <= M; ++j) {
            st[k][j] = min(st[k-1][j], st[k-1][j + half]);
        }
    }

    // prevGE/nextGE cho ngưỡng t = 0..10
    prevGE.assign(MAXV, vector<int>(M));
    nextGE.assign(MAXV, vector<int>(M));
    for (int t = 0; t < MAXV; ++t) {
        int last = -1;
        for (int j = 0; j < M; ++j) {
            prevGE[t][j] = last;
            if (Hcol[j] >= t) last = j;
        }
        int nxt = M;
        for (int j = M - 1; j >= 0; --j) {
            nextGE[t][j] = nxt;
            if (Hcol[j] >= t) nxt = j;
        }
    }
}

// ----------------- can_reach -----------------
bool can_reach(int L, int R, int S, int D) {
    // Theo đề, (0,S) và (0,D) luôn hợp lệ: T[0] > H[S], H[D] (trang 2). :contentReference[oaicite:3]{index=3}
    // Khởi tạo:
    int tcur = Trow[0];

    // Dải hàng-0 quanh D (để kết thúc ở 0): các cột trong [L,R] với H < T[0] cùng component của D
    auto dseg = span_around(L, R, D, tcur);
    int DL = dseg.first, DR = dseg.second;              // luôn DL ≤ D ≤ DR

    // Dải quanh S theo tcur
    auto sseg = span_around(L, R, S, tcur);
    int Lb = sseg.first, Rb = sseg.second;              // luôn Lb ≤ S ≤ Rb

    // Lặp mở rộng (≤ 11 vòng do miền 0..10)
    for (int iter = 0; iter < MAXV + 5; ++iter) {
        // Ẩm nhỏ nhất trong dải hiện tại ⇒ độ sâu tối đa có thể xuống thẳng
        int hmin = rmqMinH(Lb, Rb);                     // 0..10
        int rmax = lastGreater[hmin];                   // rmax ≥ 0 vì T[0] > hmin
        if (rmax < 0) return false;                     // guard

        int tnew = prefMaxT[rmax];                      // nhiệt tốt nhất trong các hàng 0..rmax
        // Dải ngang mới quanh S theo tnew
        auto sseg2 = span_around(L, R, S, tnew);
        int L2 = sseg2.first, R2 = sseg2.second;

        // Kiểm tra có thể "chui lên 0" trong dải của D sau khi mở rộng:
        int IL = max(L2, DL), IR = min(R2, DR);
        int h_on_intersection = rmqMinH(IL, IR);
        if (h_on_intersection < prefMinT[rmax]) {
            // Tồn tại cột j ∈ (component mới của S) ∩ (dải hàng-0 của D)
            // với H[j] < prefixMin(0..rmax) ⇒ leo dọc về 0 được ⇒ tới (0,D) được.
            return true;
        }

        if (tnew <= tcur) return false;                 // không thể mở rộng thêm ⇒ không thể tới
        // Cập nhật và lặp
        tcur = tnew;
        Lb = L2; Rb = R2;
    }
    return false; // guard
}

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