CF1601D Difficult Mountain
题目描述
$n$ 个人相约去爬山。
山的初始攀登难度为 $d$。
每位登山者有两个属性:技巧 $s$ 和整洁度 $a$。
技巧为 $s$ 的登山者能登上攀登难度为 $p$ 的山当且仅当 $p\leq s$。
在一位整洁度为 $a$ 的登山者登上攀登难度为 $p$ 的山后,山的攀登难度会变为 $\max(p,a)$。
请给这些登山者指定一个爬山的先后顺序,最大化登上山的人数。
如果轮到一位登山者时他能登上山,则他一定会选择登山。
输入格式
第一行两个整数 $n,d$($1\leq n\leq 5\times10^5$,$0\leq d\leq10^9$)。
接下来 $n$ 行每行两个整数 $s_i,a_i(0\leq s_i,a_i\leq 10^9)$,描述第 $i$ 个登山者的信息。
输出格式
一行一个整数,为登上山的人数的最大值。
说明/提示
In the first example, alpinists $ 2 $ and $ 3 $ can climb the mountain if they go in this order. There is no other way to achieve the answer of $ 2 $ .
In the second example, alpinist $ 1 $ is not able to climb because of the initial difficulty of the mountain, while alpinists $ 2 $ and $ 3 $ can go up in any order.
In the third example, the mountain can be climbed by alpinists $ 5 $ , $ 3 $ and $ 4 $ in this particular order. There is no other way to achieve optimal answer.