結果
| 問題 | No.1170 Never Want to Walk | 
| コンテスト | |
| ユーザー |  | 
| 提出日時 | 2025-10-08 18:22:46 | 
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) | 
| 結果 | 
                                WA
                                 
                             | 
| 実行時間 | - | 
| コード長 | 2,941 bytes | 
| コンパイル時間 | 1,992 ms | 
| コンパイル使用メモリ | 89,860 KB | 
| 実行使用メモリ | 7,720 KB | 
| 最終ジャッジ日時 | 2025-10-08 18:22:51 | 
| 合計ジャッジ時間 | 4,670 ms | 
| ジャッジサーバーID (参考情報) | judge4 / judge3 | 
(要ログイン)
| ファイルパターン | 結果 | 
|---|---|
| sample | WA * 2 | 
| other | AC * 1 WA * 36 | 
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
// 入出力の高速化
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}
class StationConnectivity {
private:
    std::vector<int> 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<int>& 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<int> 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;
}
            
            
            
        