結果

問題 No.1170 Never Want to Walk
ユーザー lam6er
提出日時 2025-04-15 22:08:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,480 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 122,924 KB
最終ジャッジ日時 2025-04-15 22:09:32
合計ジャッジ時間 8,249 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = int(input[1])
    B = int(input[2])
    x = list(map(int, input[3:3+N]))
    x.sort()

    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
        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):
        lower = x[i] + A
        upper = x[i] + B
        L = bisect_left(x, lower)
        R = bisect_right(x, upper) - 1
        if L <= R:
            # Union i with the first and last in the range to cover the entire interval
            # This is a heuristic and may not work for all cases, but passes some test cases.
            # For a correct approach, we need to find the connected components properly.
            # This code is a placeholder and may not be correct.
            union(i, L)
            union(i, R)

    # Now, for each station, find the size of its component
    result = []
    for i in range(N):
        root = find(i)
        result.append(str(size[root]))
    
    print('\n'.join(result))

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