ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Энергетическая стена

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
— Предположим, что игрок основал базу на новой планете. Чтобы оберегать её от возможного нападения местных обитателей, потребуются какие-то защитные сооружения. Давай добавим в игру сторожевые башни, которые можно будет расставить по периметру базы. При приближении противника башня будет стрелять по нему из установленной на ней лазерной пушки.
— Сторожевые башни и так были уже во всех играх. Давай придумаем что-нибудь более оригинальное. Может, окружить базу силовым полем?
— Хорошая идея. База стоит на берегу океана лавы, поэтому с этой стороны можно не ожидать нападения. А вот с другой стороны базу можно окружить энергетической стеной, состоящей из n секций. Каждая секция стены не будет зависеть от других и будет постоянно накапливать энергию. Через некоторое время после постройки стены уровня её энергии, вероятно, хватит, чтобы отбить любое нападение.
— А если противник нападёт на одну из секций стены в момент, когда та ещё не накопит достаточного количества энергии?
— Давай построим на базе резервное хранилище энергии и разрешим игроку при нападении противника направлять энергию из него на нужные секции стены. Если вдруг противник приблизится к i-й секции стены, запас из резервного хранилища можно будет использовать для усиления d-окрестности i-й секции, то есть, всех секций с (id + 1)-й по (i + d − 1)-ю (секции пронумерованы подряд, целыми числами от 1 до n). Уровень энергии i-й секции увеличится на d · x единиц, соседних с ней секций — на (d − 1) · x единиц, секций на расстоянии 2 — на (d − 2) · x единиц, и так далее. Уровень энергии секций с номерами id + 1 и i + d − 1 увеличится на x единиц энергии. Значение x следует выбирать так, чтобы использовать на усиление стены весь запас энергии из хранилища; после этого действия энергии в хранилище не останется.
— Но ведь нужно будет как-то пополнять запас энергии в хранилище. Давай предоставим игроку возможность перенести в хранилище всю энергию с нескольких соседних секций стены, если он считает, что в ближайшее время можно не опасаться нападения на них. Запасая энергию таким образом и используя её при нападении противника, игрок сможет серьёзно повысить обороноспособность базы.

Исходные данные

В первой строке записаны целые числа n и p — количество секций стены и количество энергии, накапливаемое одной секцией за единицу времени (1 ≤ n ≤ 109; 1 ≤ p ≤ 100). Во второй строке записано целое число q — количество действий игрока (1 ≤ q ≤ 105). Далее в q строках записаны эти действия. Описание действия начинается с целого числа t — времени, когда игрок совершил его (0 ≤ t ≤ 109). Далее записаны тип и параметры действия. Действия бывают двух типов: использовать энергию из хранилища на усиление d-окрестности i-й секции стены — «enforce i d» (1 ≤ in; 1 ≤ id + 1 ≤ i + d − 1 ≤ n) и перенести в хранилище всю энергию секций стены с l-й по r-ю — «save l r» (1 ≤ lrn). Все действия следует считать мгновенными и происходящими в различные моменты времени. Действия упорядочены по возрастанию t. В начальный момент времени t = 0 уровень энергии всех секций стены и запас энергии в хранилище равны нулю.

Результат

На каждый перенос энергии в хранилище выведите запас энергии в хранилище после этого переноса. Числа должны быть выведены с абсолютной или относительной погрешностью не более 10−6.

Пример

исходные данныерезультат
5 1
4
2 save 4 5
3 enforce 2 2
4 save 3 5
5 enforce 3 3
4.000000
9.000000

Замечания

Энергия секций стены после совершения каждого из действий игрока в примере: (2, 2, 2, 0, 0), (4, 5, 4, 1, 1), (5, 6, 0, 0, 0), (7, 9, 4, 3, 2).
Автор задачи: Денис Дублённых
Источник задачи: XVII Открытый чемпионат Урала по спортивному программированию (май, 2013)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1977. Энергетическая стена