結果

問題 No.2922 Rose Garden
コンテスト
ユーザー hirayuu_yc
提出日時 2025-02-07 12:15:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 259 ms / 3,000 ms
コード長 2,400 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 136,924 KB
最終ジャッジ日時 2025-02-07 12:15:57
合計ジャッジ時間 11,154 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys, math
    data = sys.stdin.read().strip().split()
    if not data: 
        return
    it = iter(data)
    n = int(next(it))
    S = int(next(it))
    B = int(next(it))
    H = [int(next(it)) for _ in range(n)]
    
    # If there is only one platform, we are already done.
    if n <= 1:
        sys.stdout.write("Yes")
        return

    # Build a sparse table for RMQ (range maximum query) on H.
    # st[k][i] will store the maximum in H[i...i+2^k - 1].
    N = n
    logN = N.bit_length()
    st = [H[:]]
    for k in range(1, logN):
        prev = st[-1]
        size = N - (1 << k) + 1
        curr = [0] * size
        for i in range(size):
            a = prev[i]
            b = prev[i + (1 << (k-1))]
            curr[i] = a if a >= b else b
        st.append(curr)
    
    # Precompute logarithms for lengths 1..N.
    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1

    def query(l, r):
        # Returns the maximum value in H[l...r] (0-indexed, inclusive)
        length = r - l + 1
        k = log_table[length]
        a = st[k][l]
        b = st[k][r - (1 << k) + 1]
        return a if a >= b else b

    # For each platform i (0-indexed), we compute F[i]: the farthest index
    # j (with i < j < n) such that every platform between i+1 and j has height <= H[i] + S*B.
    # (For i = n-1, F[i] = n-1 by definition.)
    F = [0] * N
    F[N - 1] = N - 1
    for i in range(N - 1):
        thresh = H[i] + S * B  # Allowed maximum height during the run from i.
        lo = i + 1
        hi = N - 1
        ans = i  # at least i is reachable (i.e. no move)
        # Binary search for the largest j in [i+1, N-1] with max(H[i+1..j]) <= thresh.
        while lo <= hi:
            mid = (lo + hi) >> 1
            if query(i + 1, mid) <= thresh:
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        F[i] = ans

    # Now, use a greedy jump game: from a landed state at platform i, you can
    # jump (land) to any platform in the interval {i+1, ..., F[i]}.
    farthest = 0
    i = 0
    while i < N and i <= farthest:
        if F[i] > farthest:
            farthest = F[i]
        if farthest >= N - 1:
            sys.stdout.write("Yes")
            return
        i += 1
    sys.stdout.write("No")

if __name__ == '__main__':
    solve()
0