結果

問題 No.871 かえるのうた
ユーザー lam6er
提出日時 2025-03-20 20:20:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 278 ms / 2,000 ms
コード長 2,351 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 188,636 KB
最終ジャッジ日時 2025-03-20 20:21:01
合計ジャッジ時間 7,430 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, K = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    X = list(map(int, input[ptr:ptr+N]))
    ptr += N
    A = list(map(int, input[ptr:ptr+N]))
    K -= 1  # convert to 0-based index

    left = [X[i] - A[i] for i in range(N)]
    right_arr = [X[i] + A[i] for i in range(N)]

    # Preprocess log_table
    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1
    max_level = log_table[N] + 1

    # Build sparse tables for min of left and max of right
    def build_sparse_table(arr, func):
        n = len(arr)
        st = []
        st.append(arr.copy())
        for j in range(1, max_level):
            prev = st[j-1]
            curr = []
            step = 1 << j
            for i in range(n - step + 1):
                a = prev[i]
                b = prev[i + (1 << (j-1))]
                curr.append(func(a, b))
            st.append(curr)
        return st

    # Sparse tables for min of left and max of right_arr
    min_st = build_sparse_table(left, min)
    max_st = build_sparse_table(right_arr, max)

    def query_min(l, r):
        if l > r:
            return float('inf')
        length = r - l + 1
        k = log_table[length]
        return min(min_st[k][l], min_st[k][r - (1 << k) + 1])

    def query_max(l, r):
        if l > r:
            return -float('inf')
        length = r - l + 1
        k = log_table[length]
        return max(max_st[k][l], max_st[k][r - (1 << k) + 1])

    # Initial range
    L = X[K] - A[K]
    R = X[K] + A[K]

    while True:
        # Find the current frogs in range [L, R]
        left_idx = bisect.bisect_left(X, L)
        right_idx = bisect.bisect_right(X, R) - 1

        if left_idx > right_idx:
            break

        # Get min_left and max_right in the current range
        min_left = query_min(left_idx, right_idx)
        max_right = query_max(left_idx, right_idx)

        new_L = min(L, min_left)
        new_R = max(R, max_right)

        if new_L == L and new_R == R:
            break
        L, R = new_L, new_R

    # Count frogs in the final range [L, R]
    count_left = bisect.bisect_left(X, L)
    count_right = bisect.bisect_right(X, R)
    print(count_right - count_left)

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