結果

問題 No.1170 Never Want to Walk
ユーザー Craft Boss
提出日時 2025-10-07 19:30:45
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,051 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 32,460 KB
最終ジャッジ日時 2025-10-07 19:30:56
合計ジャッジ時間 10,560 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 8 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

# 再帰の制限を緩和（Nが大きい場合に対応）
sys.setrecursionlimit(10**6)

class StationConnectivity:
    def __init__(self, num_station):
        # 親ノードを格納。負の値は根で、その絶対値がサイズを表す。
        self.parent = [-1] * num_station
        # 各連結成分の最も右（大きいインデックス）の要素のインデックスを保持
        self.rightmost = list(range(num_station))

    def find(self, i):
        """経路圧縮を行いながら根を見つける"""
        if self.parent[i] < 0:
            return i
        else:
            # 再帰的に根を探し、自身の親を直接根に付け替える
            self.parent[i] = self.find(self.parent[i])
            return self.parent[i]

    def union(self, x, y):
        """2つの要素x, yが属するグループを併合する"""
        x_root = self.find(x)
        y_root = self.find(y)

        if x_root != y_root:
            # サイズが小さい方を大きい方にマージする (union by size)
            if self.parent[x_root] > self.parent[y_root]:
                x_root, y_root = y_root, x_root
            
            # サイズを更新
            self.parent[x_root] += self.parent[y_root]
            # 親を付け替える
            self.parent[y_root] = x_root
            # 新しい根のrightmostを、併合した2つのグループのrightmostの大きい方で更新
            self.rightmost[x_root] = max(self.rightmost[x_root], self.rightmost[y_root])

    def count_reachable(self, i):
        """iから到達可能な駅の数（i自身を含む）を返す"""
        return -self.parent[self.find(i)]

def main():
    N, A, B = map(int, input().split())
    xi = list(map(int, input().split()))

    railway = StationConnectivity(N)

    # 各駅iについて、それより前の駅との連結を調べる
    for i in range(N):
        # 駅iと連結可能な駅jの座標範囲: [xi[i] - B, xi[i] - A]
        
        # 二分探索で、連結対象となりうる駅の範囲の開始インデックスを見つける
        # xi[j] >= xi[i] - B となる最初のjを探す
        left_coord = xi[i] - B
        start_index = bisect.bisect_left(xi, left_coord, hi=i)
        
        # 連結対象の駅jの座標の上限
        right_coord = xi[i] - A
        
        # start_indexからiの手前までを効率的に走査
        j = start_index
        while j < i:
            # jが連結対象範囲の上限を超えていたらループを抜ける
            if xi[j] > right_coord:
                break
            
            # iとjを連結
            railway.union(i, j)
            
            # 次に調べるjを、今連結したグループの最も右の駅の次までジャンプさせる
            j = railway.rightmost[railway.find(j)] + 1

    # 各駅について結果を出力
    for i in range(N):
        print(railway.count_reachable(i))

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