E - 高橋君とホテル / Tak and Hotels

E - 高橋君とホテル / Tak and Hotels

ホテルiからd日で移動できる場所は、「現在地点から距離がLを超えない範囲で移動する」をd回繰り返した場所です
全てのiについて1日で移動できる場所は二分探索でO(log n)
よってダブリングが出来て二分探索します

また左から右にしか移動しないと仮定してかまわないです

Submission #4178162 - AtCoder Regular Contest 060

vi a, b, c;
int can[22][k5];//jから 1<<i日で移動できる地点
int lim;
bool calc(int v, int f, int t) {
    rep(i, 22) {
        if (bget(v, i))f = can[i][f];
        if (f >= t)return 1;
    }
    return 0;
}
signed main() {
    cin >> n;
    addn(a, n);
    cin >> lim >> q;
    rep(i, n) {
        int t = upperIndex(a, a[i] + lim) - 1;
        can[0][i] = t;
    }
    rep(k, 1, 22) {
        rep(i, n) {
            can[k][i] = can[k - 1][can[k - 1][i]];
        }
    }
    while (q--) {
        int f, s;
        cin >> f >> s;
        --f, --s;
        if (f > s)swap(f, s);
        cou = 0;
        int ok = inf, ng = 0;
        while (abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (calc(mid, f, s))ok = mid;
            else ng = mid;
        }
        cout << ok << endl;
    }
    return 0;
}