結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:48:45 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,647 bytes |
コンパイル時間 | 382 ms |
コンパイル使用メモリ | 82,772 KB |
実行使用メモリ | 104,408 KB |
最終ジャッジ日時 | 2025-03-26 15:49:57 |
合計ジャッジ時間 | 9,512 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 TLE * 1 -- * 6 |
ソースコード
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() component = [] q.append(i) visited[i] = True component.append(i) while q: current = q.popleft() current_x = x[current] # Process right allowed range (current_x + a to current_x + b) lower_right = current_x + a upper_right = current_x + b left_idx = bisect.bisect_left(x, lower_right) right_idx = bisect.bisect_right(x, upper_right) - 1 if left_idx <= right_idx: for k in range(left_idx, right_idx + 1): if not visited[k]: visited[k] = True component.append(k) q.append(k) # Process left allowed range (current_x - b to current_x - a) lower_left = current_x - b upper_left = current_x - a left_left_idx = bisect.bisect_left(x, lower_left) right_left_idx = bisect.bisect_right(x, upper_left) - 1 if left_left_idx <= right_left_idx: for k in range(left_left_idx, right_left_idx + 1): if not visited[k]: visited[k] = True component.append(k) q.append(k) size = len(component) for node in component: ans[node] = size for num in ans: print(num)