import sys # sys.setrecursionlimit(200000) class StationConnectivity: def __init__(self, num_station): # parent[i] < 0 の場合、iは根ノードで、値はグループのサイズ(負の値) self.parent = [-1] * num_station # rank[i] は木の高さの上限 self.rank = [0] * num_station def find(self, id): """ 要素 id の根(ルート)を O(α(N)) で探す。(経路圧縮あり) """ 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 by Rank: ランクの低い木を高い木に結合する""" if root1 == root2: return False # すでに同じセット # ランクの比較 if self.rank[root1] < self.rank[root2]: root1, root2 = root2, root1 # 結合 self.parent[root2] = root1 # サイズの更新 self.parent[root1] += self.parent[root2] # ランクが同じ場合にのみランクを増やす if self.rank[root1] == self.rank[root2]: self.rank[root1] += 1 return True def union(self, xi, A, B): """ スライディングウィンドウ(二重ポインタ)で接続処理を O(N) に改善。 """ num_station = len(xi) j_start = 0 j_end = 0 for i in range(num_station): x = xi[i] root_i = self.find(i) # 接続元のルートを事前に取得 # 1. j_start を更新 while j_start < i and x - xi[j_start] > B: j_start += 1 # 2. j_end を更新 while j_end < i and x - xi[j_end] >= A: j_end += 1 # 3. 範囲 [j_start, j_end) の要素に対して Union を実行 for j in range(j_start, j_end): root_j = self.find(j) if root_i != root_j: # Union 操作の実行(Union by Rankを使用) self.union_sets(root_i, root_j) # root_iが変化した可能性があるため、再度ルートを取得 root_i = self.find(root_i) # ここが重要: j が root_i と同じグループなら、処理をスキップ 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()