uniの競プロlog

適当に書いていきます

【精進】ABC153 F - Silver Fox vs Monster

毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク F - Silver Fox vs Monster

解法

座標順にソートした後、単純に前から順に「 X_i が負ならcontinue, 正なら座標が X_i から X_i+2D の間にあるモンスターの体力に H_i 以上の最小の A の倍数を引く」という操作を行う。
座標が範囲内にある最大の添字は二分探索、体力の更新は遅延セグメント木を使えば O(\log N) で処理できるので、全体で O(N\log N) となる。

Submission #53801688 - AtCoder Beginner Contest 153