Submission #1256882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256882		christhegamechanger	Obstacles for a Llama (IOI25_obstacles)	C++17	10 / 100	90 ms	40248 KiB

obstacles

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

namespace Solver {
    static const int MAXV = 11; // values 0..10

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

    // Sparse Table for RMQ min on H
    vector<int> lg2;
    vector<vector<int>> st; // st[k][i] = min on [i, i+2^k-1], valid i <= M-(1<<k)

    // For each threshold t, nearest barrier with H >= t
    vector<vector<int>> prevGE, nextGE; // size [11][M]

    // prefix min/max for T
    vector<int> prefMinT, prefMaxT;

    // last index r with prefMinT[r] > h, for h=0..10
    int lastGreater[MAXV];

    inline int rmqMinH(int l, int r) {
        int len = r - l + 1;
        int k = lg2[len];
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    }

    inline pair<int,int> component_bounds(int L, int R, int S, int t) {
        // maximal contiguous block around S inside [L,R] with H < t
        int Lb = max(L, prevGE[t][S] + 1);
        int Rb = min(R, nextGE[t][S] - 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();

        // Build RMQ (sparse table) on H
        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 i = 0; i < M; ++i) st[0][i] = Hcol[i];
        for (int k = 1; k <= K; ++k) {
            int half = 1 << (k - 1);
            for (int i = 0; i + (1 << k) <= M; ++i) {
                st[k][i] = min(st[k-1][i], st[k-1][i + half]);
            }
        }

        // prevGE / nextGE for thresholds 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;
            }
            last = M;
            for (int j = M - 1; j >= 0; --j) {
                nextGE[t][j] = last;
                if (Hcol[j] >= t) last = j;
            }
        }

        // 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] = Trow[i];
                prefMaxT[i] = Trow[i];
            } else {
                prefMinT[i] = min(prefMinT[i-1], Trow[i]);
                prefMaxT[i] = max(prefMaxT[i-1], Trow[i]);
            }
        }

        // lastGreater[h] = largest r with prefMinT[r] > h
        for (int h = 0; h < MAXV; ++h) {
            int last = -1;
            for (int r = 0; r < N; ++r) if (prefMinT[r] > h) last = r;
            lastGreater[h] = last; // -1 if none
        }
    }

    bool can_reach(int L, int R, int S, int D) {
        if (S == D) return true;

        int tcur = Trow[0]; // current horizontal capability
        auto seg = component_bounds(L, R, S, tcur);
        int Lb = seg.first, Rb = seg.second;
        if (D >= Lb && D <= Rb) return true;

        // Iteratively expand capability using the best "elevator" column
        for (int iter = 0; iter < 15; ++iter) { // <= 11 really, guard 15
            int hmin = rmqMinH(Lb, Rb);
            int rmax = (hmin >= 0 && hmin < MAXV) ? lastGreater[hmin] : -1;
            if (rmax < 0) return false;
            int tnew = prefMaxT[rmax];
            if (tnew <= tcur) return false; // can't expand further
            tcur = tnew;
            seg = component_bounds(L, R, S, tcur);
            Lb = seg.first; Rb = seg.second;
            if (D >= Lb && D <= Rb) return true;
        }
        return false;
    }
} // namespace Solver

// Required interface (NO main):
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: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17