Difficult Mountain
Contest: Codeforces Round 751 (Div. 1)
Difficulty rating: 2700
Tags: data structures, dp, greedy, sortings

A group of $$$n$$$ alpinists has just reached the foot of the mountain. The initial difficulty of climbing this mountain can be described as an integer $$$d$$$.

Each alpinist can be described by two integers $$$s$$$ and $$$a$$$, where $$$s$$$ is his skill of climbing mountains and $$$a$$$ is his neatness.

An alpinist of skill level $$$s$$$ is able to climb a mountain of difficulty $$$p$$$ only if $$$p \leq s$$$. As an alpinist climbs a mountain, they affect the path and thus may change mountain difficulty. Specifically, if an alpinist of neatness $$$a$$$ climbs a mountain of difficulty $$$p$$$ the difficulty of this mountain becomes $$$\max(p, a)$$$.

Alpinists will climb the mountain one by one. And before the start, they wonder, what is the maximum number of alpinists who will be able to climb the mountain if they choose the right order. As you are the only person in the group who does programming, you are to answer the question.

Note that after the order is chosen, each alpinist who can climb the mountain, must climb the mountain at that time.

Input format:
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \leq n \leq 500\,000$$$; $$$0 \leq d \leq 10^9$$$) — the number of alpinists and the initial difficulty of the mountain.

Each of the next $$$n$$$ lines contains two integers $$$s_i$$$ and $$$a_i$$$ ($$$0 \leq s_i, a_i \leq 10^9$$$) that define the skill of climbing and the neatness of the $$$i$$$-th alpinist.

Output format:
Print one integer equal to the maximum number of alpinists who can climb the mountain if they choose the right order to do so.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
3 2
2 6
3 5
5 7

Example output:
2

Example input:
3 3
2 4
6 4
4 6

Example output:
2

Editorial:
First, discard all $$$ i $$$ such that $$$ s_i < d $$$
Instead of climbers, we will consider pairs $$$ (s_i, a_i) $$$, and also say that the set of pairs is correct if there is a permutation $$$ p_1 \ldots p_n $$$ such that for every $$$ i : \max (d, a_ {p_1}, \ldots a_ {p_ {i-1}}) \le s_ {p_i} $$$, which means that there is an order in which all climbers can climb.
We will call a pair of indices $$$ i, j $$$ incompatible if $$$ i \neq j $$$ and $$$ s_j < a_i $$$ and $$$ s_i <a_j $$$. - this means that the $$$ i $$$-th climber cannot climb after the $$$ j $$$-th and vice versa. Note that if the set does not have an incompatible pair of indices, then it is correct. The suitable order for pairs $$$ (s_i, a_i) $$$ can be reached by sorting them in increasing order of pairs $$$ {min (s_i, a_i), \max (s_i, a_i)} $$$. After sorting either $$$ i $$$-th climber can go after $$$ (i - 1) $$$-th or the pair $$$ (i - 1), i $$$ is incompatible.
$$$ \quad $$$ Let's solve the problem with an additional restriction first, namely: for each $$$ i : s_i < a_i $$$, In this case, you can use the following greedy solution:
Let $$$ D = d $$$, find among the pairs $$$ (s_i, a_i) $$$ such that $$$ D \le s_i $$$, and among such pairs - the pair with the smallest $$$ a_i $$$ - it will be the next in our order. Replace $$$ D $$$ by $$$ a_i $$$, increase the answer by 1 and repeat the algorithm. If the pair with $$$ D \le s_i $$$ does not exist, terminate the algorithm. The correctness of such an algorithm is proved by induction.
To effectively implement this solution, let's sort all the pairs $$$ (s_i, a_i) $$$ in increasing order of $$$ a_i $$$
Let's go through the indices $$$ i $$$ from 1 to $$$ n $$$
$$$ \quad $$$ If $$$ D \le s_i $$$, then add 1 to the answer and replace $$$ D $$$ with $$$ a_i $$$.
$$$ \quad $$$ Let's get back to the main problem:
Consider a pair of indices $$$ i, j $$$ such that $$$s_i < a_j \le s_j < a_i$$$
Such a pair of indices is incompatible, and if the optimal answer contains $$$ i $$$, then it can be replaced with $$$ j $$$ and the sequence will not break.
$$$ \quad $$$ $$$ s_i < s_j \Rightarrow $$$ for any value of $$$ D $$$ that matches $$$ i $$$ it matches $$$ j $$$. $$$ \quad $$$ $$$ a_j < a_i \Rightarrow $$$ for any $$$ D: max (D, a_j) \le max (D, a_i) $$$
Therefore, for any such pair $$$ i, j $$$, the $$$ i $$$-th can be excluded from the set of climbers and the answer will not worsen.
$$$ \quad $$$ To effectively remove all such $$$ (s_i, a_i) $$$ pairs, we use the two-pointer method:
Let's take out all such pairs that $$$ a_i \le s_i $$$ into the $$$ b $$$ array. Let the remaining pairs be in the $$$ c $$$ array. Let's sort the array $$$ b $$$ in increasing order of $$$ a_i $$$ and the array $$$ c $$$ in increasing order of $$$ s_i $$$. Let's create an ordered set $$$ M $$$, which can store the pairs $$$ (s_i, a_i) $$$ in decreasing order of $$$ a_i $$$. Let's create a pointer $$$ j = 0 $$$.
Let's go through the elements of the $$$ b $$$ array with index i.
$$$ \quad $$$ For this item:
$$$ \quad $$$ While $$$ c_ {j} .s < b_ {i} .a $$$ we will add $$$ c_j $$$ to the set $$$ M $$$
$$$ \quad $$$ Now while $$$ b_ {i} .s < M_ {1} .a $$$ we will delete the first element M.
Among the elements of the $$$ b $$$ array, the $$$ M $$$ set and the remaining elements in the $$$ c $$$ array, there are no more required pairs.
Note that among the remaining pairs $$$ (s_i, a_i) $$$, any pair of indices $$$ i, j $$$ such that $$$ a_i \le s_i $$$ or $$$ a_j \le s_j $$$ is not incompatible.
Now, if we find the maximum correct subset of the pairs $$$ (s_i, a_i) $$$, such that $$$ s_i < a_i $$$ and combine it with the set of pairs $$$ (s_i, a_i) $$$, such that $$$ a_i \le s_i$$$, we get the correct set, moreover, for obvious reasons – it has maximum size. Therefore, we will get the answer to the problem.