結果

問題 No.1170 Never Want to Walk
ユーザー lam6er
提出日時 2025-04-16 15:37:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,282 bytes
コンパイル時間 549 ms
コンパイル使用メモリ 81,684 KB
実行使用メモリ 123,160 KB
最終ジャッジ日時 2025-04-16 15:43:00
合計ジャッジ時間 7,507 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()
    idx = 0
    N = int(input[idx]); idx +=1
    A = int(input[idx]); idx +=1
    B = int(input[idx]); idx +=1
    x = list(map(int, input[idx:idx+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]
        left = xi + A
        right_val = xi + B
        l = bisect_left(x, left)
        r = bisect_right(x, right_val) - 1
        if l > r:
            continue
        # Connect to l and r
        if l < N:
            union(i, l)
        if r >=0 and r != l:
            union(i, r)

    # After all unions, find the root for each i and output the size
    result = []
    for i in range(N):
        root = find(i)
        result.append(str(size[root]))
    
    print('\n'.join(result))

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