Задача 6. Большой линейный коллайдер

Автор:Центральная предметно-методическая комиссия
Входной файл: linear.in   Ограничение времени:3 сек
Выходной файл: linear.out   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e, либо положительно заряженную частицу — позитрон e+. В эксперименте i-я частица исходно размещается в точке с координатой xi. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e частицы перемещаются по направлению уменьшения координаты, а e+ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

Если в процессе перемещения частицы e и e+ оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.

Ученые выбрали m различных моментов времени t1, t2, ..., tm, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени tj, не должны учитываться при подсчете количества частиц для этого момента времени.

Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.

Формат входного файла

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (x1 < x2 < x3 < ... < xn). Частица e описывается значением vi = −1, а частица e+ описывается значением vi = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t1,t2,...,tm.

Формат выходного файла

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1 ≤ n, m ≤ 200000

109 ≤ xi, m ≤ 109

0 ≤ ti ≤ 109

vi равно 1 или 1

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи
nximti
1351 ≤ n ≤ 100100 ≤ xi ≤ 100m = 10 ≤ ti ≤ 100
2121 ≤ n ≤ 100109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091
3121 ≤ n ≤ 200 000109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091, 2
4411 ≤ n ≤ 200 000109 ≤ xi ≤ 109 1 ≤ m ≤ 200 0000 ≤ ti ≤ 1091, 2, 3

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примеру

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e+ в точке 1, частица e в точке 0, частица e+ в точке 1 и частица e в точке 5.

В момент времени 0.5 первая частица e+ и первая частица e сталкиваются в точке с координатой 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

Примеры тестов

Входной файл (linear.in) Выходной файл (linear.out)
1
4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3
4
2
0
0

0.020s 0.004s 9