Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 3 сек | |
Входной файл: | linear.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | linear.out | |||
Максимальный балл: | 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
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | |||
---|---|---|---|---|---|---|
n | xi | m | ti | |||
1 | 35 | 1 ≤ n ≤ 100 | − 100 ≤ xi ≤ 100 | m = 1 | 0 ≤ ti ≤ 100 | |
2 | 12 | 1 ≤ n ≤ 100 | − 109 ≤ xi ≤ 109 | m = 1 | 0 ≤ ti ≤ 109 | 1 |
3 | 12 | 1 ≤ n ≤ 200000 | − 109 ≤ xi ≤ 109 | m = 1 | 0 ≤ ti ≤ 109 | 1, 2 |
4 | 41 | 1 ≤ n ≤ 200000 | − 109 ≤ xi ≤ 109 | 1 ≤ m ≤ 200000 | 0 ≤ ti ≤ 109 | 1, 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 |
|
|