Задача №113444. Большой линейный коллайдер
Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов «Большой линейный коллайдер» (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.
В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон \(е^–\) , либо положительно заряженную частицу — позитрон \(е^{+}\) . В эксперименте \(i\)-я частица исходно размещается в точке с координатой \(x_i\) . После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: \(е^{–}\) частицы перемещаются по направлению уменьшения координаты, а \(е^{+}\) частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.
Если в процессе перемещения частицы \(е^{–}\) и \(е^{+}\) оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.
Ученые выбрали \(m\) различных моментов времени \(t_1, t_2, \dots, t_m\), для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени \(t_j\) , не должны учитываться при подсчете количества частиц для этого момента времени.
Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.
Первая строка входного файла содержит число \(n\) — количество частиц (\(1 \le n \le 200 000\)). Последующие \(n\) строк описывают частdotsицы следующим образом: каждая строка содержит по два целых числа \(x_i\) и \(v_i\) — координату \(i\)-й частицы и ее тип соответственно (\(–10^9 \le x_1 \lt x_2 \lt \dots \lt x_n \le 10^9 , v_i\) равно –1 или 1). Частица \(е^{–}\) описывается значением \(v_i = –1\), а частица \(е^{+}\) описывается значением \(v_i = 1\).
Следующая строка содержит целое число \(m\) — количество моментов времени, которые выбрали ученые (\(1 \le m \le 200 000\)). Последняя строка содержит \(m\) целых чисел: \(t_1, t_2, \dots, t_m\) (\(0 \dots t_1 \lt t_2 \lt \dots \lt t_m \le 10^9\) ).
Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.
В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица \(е^{+}\) в точке –1, частица \(е^{–}\) в точке 0, частица \(е^{+}\) в точке 1 и частица \(е^{–}\) в точке 5.
В момент времени 0.5 первая частица \(е^{+}\) и первая частица \(е^{–}\) сталкиваются в точке с координатой –0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет
4 -1 1 0 -1 1 1 5 -1 4 0 1 2 3
4 2 0 0