#include #include #include // 入出力の高速化 void fast_io() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); } class StationConnectivity { private: std::vector parent; public: StationConnectivity(int num_station) { parent.assign(num_station, -1); } int find(int id) { if (parent[id] < 0) { return id; } return parent[id] = find(parent[id]); } void union_sets(int root1, int root2) { if (root1 == root2) { return; } if (parent[root1] > parent[root2]) { std::swap(root1, root2); } parent[root1] += parent[root2]; parent[root2] = root1; } void union_stations(const std::vector& xi, int A, int B) { int num_station = xi.size(); int j_start = 0; // j_endポインタを廃止し、Unionのループと統合します。 // これにより、接続のループ処理がシンプルになり、コンパイラの最適化が働きやすくなります。 for (int i = 0; i < num_station; ++i) { int x = xi[i]; // 1. j_start を更新 (xi[i] - xi[j_start] <= B を満たすように) // 接続可能な要素の最初のインデックスを探す。 while (j_start < i && x - xi[j_start] > B) { j_start++; } // 2. 接続可能なすべての要素に対して Union を実行 // j_endの代わりに、j=i-1からj=j_startまで逆方向にループします。 // 範囲は [j_start, i-1] のうち、xi[i] - xi[j] >= A を満たすもの。 for (int j = i - 1; j >= j_start; --j) { // 距離がA未満になったら、それより小さいjはすべてA未満なのでループを抜ける if (x - xi[j] < A) { break; } // Union-Findの操作 int root_i = find(i); int root_j = find(j); if (root_i != root_j) { union_sets(root_i, root_j); // ルートが結合されたので、iの新しいルートを取得 root_i = find(i); } } } } int countReachable(int id) { return parent[find(id)] * -1; } }; void solve() { int num_station, A, B; if (!(std::cin >> num_station >> A >> B)) return; std::vector xi(num_station); for (int i = 0; i < num_station; ++i) { std::cin >> xi[i]; } StationConnectivity railway(num_station); railway.union_stations(xi, A, B); for (int i = 0; i < num_station; ++i) { std::cout << railway.countReachable(i) << "\n"; } } int main() { fast_io(); solve(); return 0; }