結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:01:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 801 ms / 2,000 ms |
コード長 | 1,812 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,228 KB |
実行使用メモリ | 122,900 KB |
最終ジャッジ日時 | 2025-04-15 22:02:47 |
合計ジャッジ時間 | 10,885 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 A = int(data[idx]) idx += 1 B = int(data[idx]) idx += 1 x = list(map(int, data[idx:idx+N])) idx += N parent = list(range(N)) size = [1] * N def find(u): while parent[u] != u: parent[u] = parent[parent[u]] # Path compression u = parent[u] return u def union(u, v): u_root = find(u) v_root = find(v) if u_root == v_root: return # Union by size if size[u_root] < size[v_root]: u_root, v_root = v_root, u_root parent[v_root] = u_root size[u_root] += size[v_root] for i in range(N): # Process right range: j > i, x[j] in [x[i]+A, x[i]+B] lower = x[i] + A upper = x[i] + B a = bisect.bisect_left(x, lower, i + 1, N) if a < N: if x[a] > upper: pass else: b = bisect.bisect_right(x, upper, a, N) - 1 if a <= b: union(i, a) union(i, b) # Process left range: j < i, x[j] in [x[i]-B, x[i]-A] lower_left = x[i] - B upper_left = x[i] - A c = bisect.bisect_left(x, lower_left, 0, i) if c < i: if x[c] > upper_left: pass else: d = bisect.bisect_right(x, upper_left, c, i) - 1 if c <= d: union(i, c) union(i, d) # Prepare the results result = [] for i in range(N): result.append(str(size[find(i)])) print('\n'.join(result)) if __name__ == '__main__': main()