結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー Craft Boss
提出日時 2025-10-08 18:14:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,598 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 116,904 KB
最終ジャッジ日時 2025-10-08 18:14:51
合計ジャッジ時間 7,397 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
# bisect は不要になります
# sys.setrecursionlimit(200000)

class StationConnectivity:
    def __init__(self, num_station):
        self.parent = [-1] * num_station

    def find(self, id):
        if self.parent[id] < 0:
            return id
        self.parent[id] = self.find(self.parent[id])
        return self.parent[id]

    def union_sets(self, root1, root2):
        """Union-Findの結合操作（Union by Size）"""
        if self.parent[root1] > self.parent[root2]: 
            root1, root2 = root2, root1
        
        self.parent[root1] += self.parent[root2]
        self.parent[root2] = root1

    def union(self, xi, A, B):
        """
        スライディングウィンドウ（二重ポインタ）で接続処理を O(N) に改善。
        """
        num_station = len(xi)
        j_start = 0 # 接続範囲の下限 (x - B)
        j_end = 0   # 接続範囲の上限 (x - A)

        for i in range(num_station):
            x = xi[i]

            # 1. j_start を更新（範囲の下限: x - B 以上）
            # x - xi[j_start] > B である限り j_start を進める
            while j_start < i and x - xi[j_start] > B:
                j_start += 1

            # 2. j_end を更新（範囲の上限: x - A 以下）
            # x - xi[j_end] >= A である限り j_end を進める
            # j_end は i-1 を超えない
            while j_end < i and x - xi[j_end] >= A:
                j_end += 1
            
            # 3. 範囲 [j_start, j_end) の要素に対して Union を実行
            # 注意: j_end の指す要素は接続範囲から外れるため、[j_start, j_end - 1] の範囲を処理します
            for j in range(j_start, j_end):
                x_root = self.find(i)
                upTox_root = self.find(j)
                
                if x_root != upTox_root:
                    self.union_sets(x_root, upTox_root)
    
    def countReachable(self, id):
        return self.parent[self.find(id)] * -1
    
        
def main():
    # 高速な入力処理
    data = sys.stdin.read().split()
    if not data:
        return

    num_station = int(data[0])
    A = int(data[1])
    B = int(data[2])
    xi = [int(x) for x in data[3:3 + num_station]]

    # O(N) の Union-Find 実行
    railway = StationConnectivity(num_station)
    railway.union(xi, A, B)

    # 高速な出力処理
    output = []
    for i in range(num_station):
        output.append(str(railway.countReachable(i)))
    
    sys.stdout.write('\n'.join(output) + '\n')

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