結果
| 問題 | No.1170 Never Want to Walk | 
| コンテスト | |
| ユーザー |  | 
| 提出日時 | 2025-10-08 18:20:53 | 
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) | 
| 結果 | 
                                TLE
                                 
                             | 
| 実行時間 | - | 
| コード長 | 3,227 bytes | 
| コンパイル時間 | 2,491 ms | 
| コンパイル使用メモリ | 100,660 KB | 
| 実行使用メモリ | 15,940 KB | 
| 最終ジャッジ日時 | 2025-10-08 18:21:06 | 
| 合計ジャッジ時間 | 7,958 ms | 
| ジャッジサーバーID (参考情報) | judge3 / judge4 | 
(要ログイン)
| ファイルパターン | 結果 | 
|---|---|
| sample | AC * 2 | 
| other | AC * 30 TLE * 1 -- * 6 | 
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
// 入出力の高速化
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}
class StationConnectivity {
private:
    std::vector<int> parent; // 根ノードの場合、値はグループのサイズ * (-1)
public:
    StationConnectivity(int num_station) {
        // 全要素を-1で初期化(各要素が独立したグループでサイズ1)
        parent.assign(num_station, -1);
    }
    // 経路圧縮ありの find 操作
    int find(int id) {
        if (parent[id] < 0) {
            return id;
        }
        // 経路圧縮
        return parent[id] = find(parent[id]);
    }
    // サイズによる統合 (Union by Size)
    void union_sets(int root1, int root2) {
        if (root1 == root2) {
            return;
        }
        // サイズの大きい方に小さい方を結合
        if (parent[root1] > parent[root2]) { // parent[i] は負の値なので、値が大きい(絶対値が小さい)方がサイズが小さい
            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; // 接続範囲の下限ポインタ
        int j_end = 0;   // 接続範囲の上限ポインタ
        for (int i = 0; i < num_station; ++i) {
            int x = xi[i];
            // 1. j_start を更新 (xi[i] - xi[j_start] <= B を満たすように)
            // Python: while j_start < i and x - xi[j_start] > B: j_start += 1
            while (j_start < i && x - xi[j_start] > B) {
                j_start++;
            }
            // 2. j_end を更新 (xi[i] - xi[j_end] >= A を満たすように)
            // Python: while j_end < i and x - xi[j_end] >= A: j_end += 1
            while (j_end < i && x - xi[j_end] >= A) {
                j_end++;
            }
            
            // 3. 範囲 [j_start, j_end) の要素に対して Union を実行
            for (int j = j_start; j < j_end; ++j) {
                int root_i = find(i);
                int root_j = find(j);
                
                if (root_i != root_j) {
                    union_sets(root_i, root_j);
                }
            }
        }
    }
    
    // 連結な駅の数を返す
    int countReachable(int id) {
        // parent[root] * -1 がサイズ
        return parent[find(id)] * -1;
    }
};
void solve() {
    // 1. 入力
    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];
    }
    // 2. Union-Findの実行 (O(N * α(N)))
    StationConnectivity railway(num_station);
    railway.union_stations(xi, A, B);
    // 3. 出力
    for (int i = 0; i < num_station; ++i) {
        std::cout << railway.countReachable(i) << "\n";
    }
}
int main() {
    // 入出力高速化関数を呼び出し
    fast_io();
    solve();
    return 0;
}
            
            
            
        