Educational Codeforces Round 90 (Rated for Div. 2) - G. Pawns

問題リンク

解説

(x, y)が k列目にいくときの、 y座標の最小値を tとする。

ここで、明らかなこととして、 t以上のポーンの個数が c個あれば、必ず 行数 \geq t + c - 1であることが必要である。

で実はこれが十分であることも示せるらしい(Editorial曰くHallの定理を使うといいらしい)

上を実現するのは遅延セグ木で簡単にできるので、求めることができました

提出コード

codeforces.com