https://emtubasa.hateblo.jp/entry/2019/05/26/133542

解法

$sum[i] = i$ 枚目のカードを用いて通ることができるゲートの個数

とすると、 $sum[i] = M$ となるような $i$ の個数が答えになります。
ということで、各ゲートについて与えられる区間 $[L_{j},R_{j}]$ について、 $sum[L_{j}],sum[L_{j}+1],...sum[R_{j}]$ に1を追加する、という操作をしてあげれば、 $i$ 枚目のカードを用いて通ることができるゲートの個数を求めることができます。
単純に加算していくと間に合わないので、いもす法を用います。
$sum[L_{j}]$ に1を加算し、 $sum[R_{j}+1]$ から1を減らしてあげて、 $sum[1]$ から順番に累積和を取っていくと、 $O(N)$ で求めることができます。

感想

本番は、いもす法を利用して脳死で解きましたが、よくよく考えると $L_{i}$ の最大値と $R_{i}$ の最小値だけを見ればよいのですね…
$N$ の制約が大きいと解くのに時間がかかった可能性があります。