Задача №114972. Зима в городе К
Город К расположен на севере очень большой страны. И вот наконец-то в этот город пришла зима, которая продлится \(m\) дней. В городе К живут самые обычные люди большой страны, поэтому они очень не любят, когда их дом покрыт снегом.
Всего в этом городе \(n\) домов, каждый из которых изначально не покрыт снегом. Вы знаете, что утром \(i\)-го зимнего дня произойдет одно из следующих событий:
- Выпадет снег, и дома с номерами от \(l_i\) до \(r_i\) включительно покроются снегом.
- Коммунальные службы очистят от снега дома с номерами от \(l_i\) до \(r_i\) включительно.
Начиная с этого момента, Вы — мэр города К. Первое ваше задание на посту мэра — спрогнозировать уровень счастья каждого жителя. Для этого вам нужно узнать, сколько дней во время зимы каждый дом не будет покрыт снегом.
Первая строка содержит два числа \(n\) и \(m\) (\(1 \leq n, m \leq 200\,000\)) — количество домов в городе К, а также длительность зимы.
В следующих \(m\) строках описываются события, которые происходили в каждый из дней зимы. В \(i\)-й строке содержится символ \(c_i\) и два целых числа \(l_i\) и \(r_i\) (\(c_i = +\) или \(c_i = -\), \(1 \leq l_i \leq r_i \leq n\)). Если \(c_i = +\), то в \(i\)-й день выпал снег на отрезке домов с \(l_i\)-го по \(r_i\)-й. Если \(c_i = -\), то в \(i\)-й день был убран весь снег с домов с \(l_i\)-го по \(r_i\)-й.
Для каждого дома выведите количество дней, которые он не будет покрыт снегом.
Рассмотрим первый пример.
В первый день зимы под снегом не будет дома \(4\).
Во второй день зимы под снегом не будут домов \(1, 2, 4\).
В третий день зимы под снегом не будет дома \(1\).
Поэтому ответ \(2\) \(1\) \(0\) \(2\).
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | Необх. группы | Комментарий | |
| 0 | 0 | – | – | – | Тесты из условия. | |
| 1 | 14 | \(n \le 1000\) | \(m \le 1000\) | 0 | ||
| 2 | 19 | – | – | – | \(l_i = r_i\) | |
| 3 | 22 | – | – | – | \(l_i = 1\) | |
| 4 | 18 | – | – | – | Если \(c_i =\) + , \(c_j =\) - , то \(i | lt; j\). |
| 5 | 27 | – | – | 0–4 | ||
4 3 + 1 3 - 1 2 + 2 4
2 1 0 2
8 5 + 1 3 + 5 8 - 2 8 - 3 7 + 1 6
0 2 2 4 3 3 4 4