Codeforces Round 745 (Div. 1) |
---|
Закончено |
Кавасиро Нитори — талантливый инженер. Поэтому ее назначили ответственной по обслуживанию поездов.
Всего существуют $$$n$$$ моделей поездов, и в депо, в котором работает Нитори, в любой момент времени будет не более одного поезда каждой модели. Изначально в депо нет поездов, и в каждый из следующих $$$m$$$ дней либо один поезд будет добавлен в депо, либо один поезд будет убран из депо. Когда добавляется поезд $$$i$$$-й модели в день $$$t$$$, он будет работать $$$x_i$$$ дней (включая день $$$t$$$), затем будет на ремонте в течение $$$y_i$$$ дней, затем опять работать $$$x_i$$$ дней, и так далее до тех пор, пока его не уберут из депо.
Чтобы следить за обслуживанием было проще, Нитори просит вас посчитать для каждого из дней, сколько поездов будут на ремонте в этот день.
В день, когда поезд убирают, он не считается находящимся в ремонте.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$).
Каждая $$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i,y_i$$$ ($$$1 \le x_i,y_i \le 10^9$$$).
Далее следуют $$$m$$$ строк, содержащих два целых числа $$$op$$$ и $$$k$$$ ($$$1 \le k \le n$$$, $$$op = 1$$$ или $$$op = 2$$$). Если $$$op=1$$$, это означает, что в этот день добавляется поезд $$$k$$$-й модели, иначе поезд модели $$$k$$$ убирают. Гарантируется, что когда добавляется поезд модели $$$x$$$, в депо нет поездов такой модели, а когда поезд модели $$$x$$$ убирают, в депо есть такой поезд.
Выведите $$$m$$$ строк, каждая $$$i$$$-я из которых содержит одно целое число, обозначающее количество поездов, находящихся на ремонте в $$$i$$$-й день.
3 4 10 15 12 10 1 1 1 3 1 1 2 1 2 3
0 1 0 0
5 4 1 1 10000000 100000000 998244353 1 2 1 1 2 1 5 2 5 1 5 1 1
0 0 0 1
Рассмотрим первый пример.
Первый день: Нитори добавляет поезд модели $$$3$$$. Работает только поезд модели $$$3$$$, и ни один поезд не находится в ремонте.
Второй день: Нитори добавляет поезд модели $$$1$$$, поезд модели $$$1$$$ работает, а поезд модели $$$3$$$ находится в ремонте.
Третий день: Нитори убирает поезд модели $$$1$$$. Ситуация такая же, как и в первый день.
Четвертый день: Нитори убирает поезд модели $$$3$$$. Нет ни одного поезда.
Название |
---|