Points and segments

You are given $n$ segments and $m$ points on a number line. For every point find how many segments contain it. Point $x$ belongs to the segment with ends $a$ and $b$ if $\min(a, b) \le x \le \max(a, b)$.

The first line contains $n$ and $m$ ($1 \le n, m \le 10^5$). The next $n$ lines contain $a_i$ and $b_i$ — the ends of a segment (in any order). The last line contains $m$ integers — the points. All numbers are at most $10^9$ in absolute value.

A single line with $m$ numbers — one for every point, in input order.

Checking every pair is $O(nm)$ — $10^{10}$ operations. The number of segments containing $x$ is (segments with left end $\le x$) − (segments with right end $< x$). Sort the left and right ends separately and find both counts for every point with binary search: $O((n + m) \log n)$.

The ends may be given in reverse order ($5\ 1$) — order them first. A point at an end of a segment belongs to it.

Source: acmp.ru, problem 396.