Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 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 |
|
|