06/04/2025 22:20:21

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2232. Подсчет пингвинов

Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Для наблюдения за пингвинами Том установил в ущелье камеры. Время от времени с камер поступает информация о передвижениях пингвинов, и иногда Том делает запросы о количестве стай пингвинов на некотором участке ущелья. Стаей считается последовательность пингвинов без промежутков, отделенная пустым пространством от других стай.

Первая строка ввода содержит два целых числа

$n$ (длина ущелья) и

$m$ (

$1\ ≤\ n\ ≤\ 100000$ ,

$1\ ≤\ m\ ≤\ 100000$ ). Далее следует

$m$ строк, содержащих хронологически упорядоченную последовательность запросов Тома и поступлений информации с камер. Первым символом в строке указывается символ '?', '*' или '.', за которым через пробел следуют два числа

$p_1$ и

$p_2$ (

$1\ ≤\ p_1\ ≤\ p_2\ ≤\ n$ ), задающих участок ущелья. Cимвол '?' означает запрос Тома о количестве стай пингвинов на участке. Cимвол '*' означает, что все позиции на заданном участке заполнились пингвинами, символ '.' означает, что все позиции на заданном участке стали свободными. Первоначально все позиции в ущелье свободны.

Для каждого запроса Тома вывести на отдельной строке количество стай пингвинов, которые видны полностью или частично на заданном участке ущелья.

Пример ввода

Пример вывода

2
3

17/10/2015	Личные соревнования по спортивному программированию (F)
14/07/2016	Лето 2016 - 9 (C)