Codeforces Round 625 (Technocup 2020 Final Round)

A. Journey Planning

$i-b_i$ が一定のところしかとれません・一定のところは全部とれます．

各移動それぞれについて「必ず navi 通りである（唯一の最短路方向である）」「navi 通りかもしれないし違反したかもしれない（複数ある最短路方向のひとつである）」「必ず navi に違反している（最短路方向ではない）」を判別すればよいです．

購入する $a$ のレベルをインクリメントしながら，各 $b$ を選んだ場合の利得の列を管理することを考えると，区間加算と区間 max 取得のできる遅延セグメント木で解けます．

操作は「0」と「11」の交換ですが，111→111 という何もしない変換により「1」と「11」の交換もできます．結局 11 という塊は好きな場所に移動できます．

よって一致判定は，11 を可能な限り削除した列を考えて一致するか（と個数の自明な条件）で行うことができます．これを Rolling Hash により行います．

興味のある点（とそれらの lca として書ける点）だけを残して木を圧縮します．この木の大きさは $O(k+m)$ になります．よって木の大きさを $n$ として $O(n)$ 時間程度でクエリを解ければよいです．

それでも愚直なシミュレーションでは間に合いませんが，他のウイルスに邪魔されないと想定した場合に重要な点が占有される予定時刻を prique で持って，その最初のイベントから消化していくようにすれば $O(n\log n)$ 時間でクエリに答えられます．

ucup に 2 次元版が出ているのですぐに解けました．順序としてはこっちが既出元ということになるはず．

各方向から見て，なるべく近い場所に目的の値を書きこもうとします．それで衝突が起きなければ目的達成です．

衝突が起きた場合には，衝突したマスを禁止して，「なるべく近い場所」を更新します．衝突がある間これを繰り返していけばよいです．