結果

問題 No.1170 Never Want to Walk
ユーザー lam6er
提出日時 2025-03-31 17:30:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,671 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 130,808 KB
最終ジャッジ日時 2025-03-31 17:31:13
合計ジャッジ時間 8,975 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    A = int(data[1])
    B = int(data[2])
    x = list(map(int, data[3:3 + n]))
    
    visited = [False] * n
    ans = [0] * n
    
    for i in range(n):
        if not visited[i]:
            queue = deque()
            component = []
            queue.append(i)
            visited[i] = True
            component.append(i)
            while queue:
                u = queue.popleft()
                # Check left adjacency
                min_x_left = x[u] - B
                max_x_left = x[u] - A
                left_start = bisect.bisect_left(x, min_x_left)
                left_end = bisect.bisect_right(x, max_x_left)
                for j in range(left_start, left_end):
                    if j != u and not visited[j]:
                        visited[j] = True
                        component.append(j)
                        queue.append(j)
                # Check right adjacency
                min_x_right = x[u] + A
                max_x_right = x[u] + B
                right_start = bisect.bisect_left(x, min_x_right)
                right_end = bisect.bisect_right(x, max_x_right)
                for j in range(right_start, right_end):
                    if j != u and not visited[j]:
                        visited[j] = True
                        component.append(j)
                        queue.append(j)
            size = len(component)
            for node in component:
                ans[node] = size
    
    for a in ans:
        print(a)

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