結果

問題 No.1170 Never Want to Walk
ユーザー lam6er
提出日時 2025-04-15 21:59:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,695 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 104,268 KB
最終ジャッジ日時 2025-04-15 22:00:19
合計ジャッジ時間 8,431 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import deque

n, A, B = map(int, input().split())
x = list(map(int, input().split()))
visited = [False] * n
ans = [0] * n

for i in range(n):
    if not visited[i]:
        q = deque()
        q.append(i)
        visited[i] = True
        component = []
        while q:
            current = q.popleft()
            component.append(current)
            # Check right range [x+A, x+B]
            lower = x[current] + A
            upper = x[current] + B
            left = bisect.bisect_left(x, lower)
            right = bisect.bisect_right(x, upper) - 1
            # Process all unvisited stations in [left, right]
            if left <= right:
                # Iterate from left to right and add unvisited stations
                j = left
                while j <= right:
                    if not visited[j]:
                        visited[j] = True
                        q.append(j)
                    j += 1
            # Check left range [x-B, x-A]
            lower = x[current] - B
            upper = x[current] - A
            left = bisect.bisect_left(x, lower)
            right = bisect.bisect_right(x, upper) - 1
            # Process all unvisited stations in [left, right]
            if left <= right:
                # Iterate from left to right and add unvisited stations
                j = left
                while j <= right:
                    if not visited[j]:
                        visited[j] = True
                        q.append(j)
                    j += 1
        # Assign component size to all members
        size = len(component)
        for j in component:
            ans[j] = size

for a in ans:
    print(a)
0