Цитирую полный текст задачи:
Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.
Формат входного файла
Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.
Формат выходного файла
Выведите M чисел – толщину носкового покрытия в каждой точке.
На первый взгляд, задача кажется весьма простой. Но, используя те поверхностные идеи для ее решения, она часто не проходит по времени (1 секунда). Собственно, был бы очень рад послушать ваши идеи алгоритмов для ее решения.
P.S. Авторы дают небольшую подсказку: использовать сортировку.
M
может быть большим, одновременный проход по двум массивам (как при merge sort'е).