No.33 アメーバがたくさん

X[i] が最大 10^9 とかなんでまともに配列を確保したりすると TLE する。T 時間後に同じ座標に到達するものたちを一つにまとめて、間と前後を埋めるようにすればよい。
方針はあっていたのに abs(X[i]-X[j]) と書くべきところを (X[i]-X[j]) と書いてしまい WA してしまった...orz。

class ManyAmeba {
public:
    void solve(void) {
            int N,D,T;
            cin>>N>>D>>T;
            vector<ll> X(N);
            REP(i,N)
                cin>>X[i];
            sort(RANGE(X));

            UFTree uft(N);
            // O(N^2*A)
            REP(i,N)
            FOR(j,i,N)
            {
                // 時間 T 以内で同じ座標に到達しうるもの同士をまとめる
                // 距離の差が D 倍なら T が十分に大きいとき同じ座標に到達する。
                // X[i],X[j] 双方から進んでくるとみなせるので距離の差の半分を T 時間内の
                // 移動できるなら条件を満たす。
                if (abs(X[i]-X[j])%D==0 && abs(X[i]-X[j])/D <= 2*T)
                    uft.unite(i,j);
            }
            map<int,pair<ll,ll>> group;
            // まとめたものの最大・最小位置を求める
            REP(i,N)
            {
                // 初期化
                if (!group.count(uft[i]))
                    group.emplace(piecewise_construct,
                                  forward_as_tuple(uft[i]),
                                  forward_as_tuple(X[i],X[i]));

                auto &rng = group[uft[i]];
                rng.first  = min(rng.first,  X[i]);
                rng.second = max(rng.second, X[i]);
            }
            ll sum = 0;
            // 計算
            for (auto g : group)
            {
                ll b,e;
                tie(b,e) = g.second;
                // 前後を埋める
                sum += 2*T;
                // 中間を埋める
                sum += ((e-b)/D+1);
            }
            cout<<sum<<endl;
    }
};