[AtCoder] ABC 127 C – Prison

問題

方針

\( 1 \) 枚のカードで全てのゲートを通過できるとは?

\( 1 \) 枚のカードで全てのゲートを通過できるとはどいうことかを考えます。ID が \( a \) のカードが全てのゲートを通過できるとき、全てのゲート \( i \) について、\( L_i \leq a \leq R_i \) を満たしている必要があります。このような \( a \) を \( 1 \leq a \leq N \) の範囲で調べる必要があります。

いもす法

\( a \) を変化させて、全てのゲートに対して調べるには計算量が多くなってしまうので、効率的な方法を考えます。この問題は、ある点において、区間の数が何個入るかを求めればよいので、いもす法を使います。\( M \) 個の区間が重なる個数が答えになります。いもす法を使うと次のような配列が得られます。

入力例 1

区間の数 \( 1 \) \( 2 \) \( 2 \) \( 2 \)
ID \( 1 \) \( 2 \) \( 3 \) \( 4 \)

入力例 2

区間の数 \( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 2 \) \( 3 \) \( 2 \) \( 1 \) \( 1 \) \( 0 \)
ID \( 1 \) \( 2 \) \( 3 \) \( 4 \) \( 5 \) \( 6 \) \( 7 \) \( 8 \) \( 9 \) \( 10 \)

また、いもす法については、次のサイトを参照してください。

いもす研 – いもす法

satanic – Imos法(いもす法)

コード

提出したコード

いもす法