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()