- Описание
- Отправленные решения
111. Точки и отрезки
Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) $\le$ x $\le$ max(a, b).
Формат ввода
Первая строка содержит два целых числа n (1 $\le$ n $\le$ $10^5$) – число отрезков и m (1 $\le$ m $\le$ $10^5$) – число точек. В следующих n строках по два целых числи $a_i$ и $b_i$ – координаты концов соответствующего отрезка. В последней строке m целых чисел – координаты точек. Все числа по модулю не превосходят $10^9$
Формат вывода
В выходной файл выведите m чисел – для каждой точки количество отрезков, в которых она содержится.
Ограничения
Ограничение времени
3 с
Ограничение памяти
256 МБ
Пример 1
Ввод
3 2
0 5
-3 2
7 10
1 6
Вывод
2 0