Codeforces Round 731 (Div. 3) E – Air Conditioners を解いた記録

問題の概要

\(1\)から\(n\)までの番号が付けられた\(n\)個の部屋が左から順に並んでおり，そのうち\(k\)個の部屋にエアコンが配置されている．
\(i\)個目のエアコンは部屋\(a_{i}\)に置かれており，そのエアコンの設定温度は\(t_{i}\)である．

部屋\(i\)の温度は次式で表される．各部屋の温度を求め，出力せよ．
\[
\min_{1 \leq j \leq k} (t_{j}+|a_{j}-i|)
\]

問題へのリンク

制約

• \(1 \leq n \leq 3 \times 10^{5}\)
• \(1 \leq k \leq n\)
• \(1 \leq a_{i} \leq n\)
• \(1 \leq t_{i} \leq 10^{9}\)
• 入力はすべて整数

解法

いったん各エアコンが自身のある部屋とその右側の部屋のみを冷やすと考えると，各部屋の温度は左から累積minのようなものを計算することで求められます．
部屋を移動するごとに温度が1度上がり，エアコンに遭遇したら（エアコンの設定温度が低ければ）温度が下がる…といった感じです．
同様の計算を右からも行えば，各部屋の温度を求められます．

実装例