毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク
F - Silver Fox vs Monster
解法
座標順にソートした後、単純に前から順に「 が負ならcontinue, 正なら座標が
から
の間にあるモンスターの体力に
以上の最小の
の倍数を引く」という操作を行う。
座標が範囲内にある最大の添字は二分探索、体力の更新は遅延セグメント木を使えば で処理できるので、全体で
となる。
毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク
F - Silver Fox vs Monster
座標順にソートした後、単純に前から順に「 が負ならcontinue, 正なら座標が
から
の間にあるモンスターの体力に
以上の最小の
の倍数を引く」という操作を行う。
座標が範囲内にある最大の添字は二分探索、体力の更新は遅延セグメント木を使えば で処理できるので、全体で
となる。