結果

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

ソースコード

diff # 

import bisect

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]))
    
    parent = list(range(N))
    size = [1] * N
    
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    
    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root == v_root:
            return
        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):
        xi = x[i]
        low = xi + A
        high = xi + B
        j = bisect.bisect_left(x, low)
        if j >= N or x[j] > high:
            continue
        k = bisect.bisect_right(x, high) - 1
        if j <= k:
            union(i, j)
            union(i, k)
    
    result = [size[find(i)] for i in range(N)]
    print('\n'.join(map(str, result)))
    
if __name__ == "__main__":
    main()
0