— Предположим, что игрок основал базу на новой планете. Чтобы оберегать
её от возможного нападения местных обитателей, потребуются какие-то
защитные сооружения. Давай добавим в игру сторожевые башни, которые можно
будет расставить по периметру базы. При приближении противника башня будет
стрелять по нему из установленной на ней лазерной пушки.
— Сторожевые башни и так были уже во всех играх. Давай придумаем
что-нибудь более оригинальное. Может, окружить базу силовым полем?
— Хорошая идея. База стоит на берегу океана лавы, поэтому с этой
стороны можно не ожидать нападения. А вот с другой стороны базу можно
окружить энергетической стеной, состоящей из n секций. Каждая секция
стены не будет зависеть от других и будет постоянно накапливать энергию.
Через некоторое время после постройки
стены уровня её энергии, вероятно, хватит, чтобы отбить любое нападение.
— А если противник нападёт на одну из секций стены в момент, когда та ещё не накопит
достаточного количества энергии?
— Давай построим на базе
резервное хранилище энергии и разрешим игроку при нападении
противника направлять энергию из него на нужные секции стены.
Если вдруг противник приблизится к i-й секции стены,
запас из резервного хранилища можно будет использовать для усиления
d-окрестности i-й секции, то есть, всех секций
с (i − d + 1)-й по (i + d − 1)-ю (секции пронумерованы подряд,
целыми числами от 1 до n). Уровень энергии i-й секции увеличится на
d · x единиц, соседних с ней секций — на (d − 1) · x единиц,
секций на расстоянии 2 — на (d − 2) · x единиц, и так далее. Уровень
энергии секций с номерами i − d + 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 ≤ i ≤ n; 1 ≤ i − d + 1 ≤ i + d − 1 ≤ n)
и перенести в хранилище всю энергию секций
стены с l-й по r-ю — «save l r» (1 ≤ l ≤ r ≤ n).
Все действия следует считать мгновенными и происходящими в различные моменты времени.
Действия упорядочены по возрастанию 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)