#include #include #include #include /** * @brief 駅の連結情報を管理するUnion-Findデータ構造を実装したクラス */ class StationConnectivity { private: // 各要素の親を格納する配列。 // 負の値はその要素が根であることを示し、その絶対値が集合のサイズを表す。 std::vector parent; public: /** * @brief コンストラクタ * @param num_station 駅の総数 */ StationConnectivity(int num_station) : parent(num_station, -1) {} /** * @brief 指定された駅が属する集合の根(代表駅)を見つける * @param id 駅のインデックス * @return int 集合の根のインデックス */ int find(int id) { // 自身が根であれば、自身のインデックスを返す if (parent[id] < 0) { return id; } // 親を再帰的にたどり、経路圧縮を行う return parent[id] = find(parent[id]); } /** * @brief 2つの駅が属する集合を1つに統合する * @param id1 駅1のインデックス * @param id2 駅2のインデックス */ void unite(int id1, int id2) { int root1 = find(id1); int root2 = find(id2); if (root1 != root2) { // サイズが小さい集合を大きい集合に統合する (union by size) if (parent[root1] > parent[root2]) { std::swap(root1, root2); // root1がより大きい集合の根になるように } // サイズを更新 parent[root1] += parent[root2]; // 小さい方の集合の根を大きい方の根に接続 parent[root2] = root1; } } /** * @brief 指定された駅から到達可能な駅の総数を返す * @param id 駅のインデックス * @return int 到達可能な駅の総数 */ int countReachable(int id) { return -parent[find(id)]; } }; /** * @brief メイン処理 */ int main() { // C++の標準入出力の高速化 std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); // --- 入力処理 --- int num_station, A, B; std::cin >> num_station >> A >> B; std::vector xi(num_station); for (int i = 0; i < num_station; ++i) { std::cin >> xi[i]; } // --- メインロジック --- StationConnectivity railway(num_station); // 全ての駅のペアをチェックし、条件を満たすなら接続する (O(N^2)の処理) for (int i = 0; i < num_station; ++i) { for (int j = 0; j < i; ++j) { int distance = xi[i] - xi[j]; if (distance >= A && distance <= B) { railway.unite(i, j); } } } // --- 出力処理 --- for (int i = 0; i < num_station; ++i) { std::cout << railway.countReachable(i) << "\n"; } return 0; }