codeFlyer （bitFlyer Programming Contest）オープンコンテスト : B - 交通費

問題
解法
解答

問題

x 軸上に N 人の人がいる。ある x 軸上の点 c をおき、そこから d 以内の人には abs(x - c) だけ交通費が支払われ、c から d より遠い人は一律で d 払われる（つまり、min(abs(x - c), d)）。これを Q 回行うとき、それぞれ全体の交通費はいくらになるかそれぞれ Q 回求める、という問題。

解法

とりあえず、Q 回ごとに分けて考える。c から d より遠い人は一律の交通費なので、これに当てはまる参加者は std::lower_bound() や std::upper_bound() で数えられる。また、c から d 以内の距離の参加者は当然連続している区間にいるので累積和を使って c からどれだけ離れているかの距離の和を求める。そうすれば O(QlogN) で間に合う。