ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Energy Wall

Time limit: 2.0 second
Memory limit: 64 MB
‘Assume that a player has built a base on a new planet. Then he needs some protective shelters to guard the base from a possible attack by locals. Let’s add watch towers to the game. The player can arrange towers along the perimeter of the base and equip them with laser guns. At the approach of the enemy, the towers will fire guns at them.’
‘Watch towers are a commonplace in all games. Let’s invent something new. What if we protect the base with a force field?’
‘A good idea. The base is located at the shore of a lava ocean, so it won’t be attacked from that side. And the other side can be protected by an energy wall consisting of n sections. Each section is an independent unit and constantly accumulates energy.’
‘What if the enemy attack comes too early or happens to be too strong for a particular section?’
‘Let’s build an energy repository at the base and allow the player to transfer energy from it to any sections of the wall in the case of an enemy attack. If enemy units approach the i-th section of the wall, the player can use the energy stored in the repository to enforce the d-area of the i-th section, i.e. sections with numbers from (id + 1) to (i + d − 1) (the sections are numbered consecutively by integers from 1 to n). The energy of the i-th section will increase by d × x units, the energy of the adjacent sections will increase by (d − 1) × x units, the energy of the sections at distance 2 will increase by (d − 2) × x units, and so on. The energy of the sections with numbers id + 1 and i + d − 1 will increase by x energy units. The value of x should be selected so as to use all the energy stored in the repository for an enforcement of the wall. After the enforcement, there will be no energy left in the repository.’
‘There must be a possibility to refill the repository. Let’s make it possible for the player to transfer all the energy from some sections of the wall to the repository if he thinks that these sections won’t be attacked in the near future. The player will store energy and use it in the case of attacks, and so the base will be well protected.’


The first line contains integers n and p, which are the number of wall sections and the amount of energy accumulated by each section in a unit of time (1 ≤ n ≤ 109; 1 ≤ p ≤ 100). The second line contains the number q of the player’s actions (1 ≤ q ≤ 105). The following q lines describe these actions in the same order they took place. Each description starts with an integer t, which is the time when the action was performed (0 ≤ t ≤ 109). Then you are given the type and parameters of the action. There can be two types of actions: “enforce i d” (1 ≤ in; 1 ≤ id + 1 ≤ i + d − 1 ≤ n) means the use of energy from the repository to enforce the d-area of the i-th section of the wall, and “save l r” (1 ≤ lrn) means the transfer of the whole energy of the sections with numbers from l to r to the repository. Each action’s duration can be neglected, no two actions have happened at the same moment of time. At the initial time t = 0, the energy level of each wall section and the amount of energy stored in the repository are zero.


For each “save” action output the current amount of saved energy, including the just saved one. The answer should be given with absolute or relative error at most 10−6.


5 1
2 save 4 5
3 enforce 2 2
4 save 3 5
5 enforce 3 3


The energies of the wall sections after each of the player’s actions in the example are as follows: (2, 2, 2, 0, 0), (4, 5, 4, 1, 1), (5, 6, 0, 0, 0), (7, 9, 4, 3, 2).
Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013
To submit the solution for this problem go to the Problem set: 1977. Energy Wall