SANTA1  Reindeer Games
With the presents all crafted and packed into Santa's sack, it's almost time for his annual trip across the world, spreading cheer to all! However, he's first taking the time to experiment with various combinations of reindeer to pull his sleigh. For a successful journey, they'll have to work productively!
Every reindeer has a unique name (a string of up to 20 casesensitive letters), as well as a seniority and a productivity value (both positive integers no larger than $10^6$). When a group of reindeer is chosen to pull the sleigh, they line up in single file, always in descending order of seniority from the front. If multiple reindeer have the same seniority, they line up in descending order of productivity within themselves (no two reindeer have both the same seniority and the same productivity). The productivity of a pair of adjacent reindeer in the lineup is the product of their individual productivity values, and the total productivity of the lineup is the sum of all such productivities. The total productivity of a group of fewer than 2 reindeer is 0.
Starting with an empty group of reindeer, Santa will perform $M$ ($1 \leq M \leq 10^5$) modifications. The $i$th modification will involve the reindeer with name $N_i$. If $A_i=$ 'A', then this reindeer will be added to the lineup (in its correct spot)  in this case, its seniority and productivity values, $S_i$ and $P_i$, will be given. Otherwise, if $A_i=$ 'R', then this reindeer will be removed from the lineup. Each reindeer will only be added once, and will only be removed if it's currently in the lineup.
To track which combinations of reindeer are more effective than others, Santa would like you to calculate the total productivity of the lineup after every modification made to it. Quickly, now, Christmas won't wait!
Input
First line: $M$
Next $M$ lines: $A_i$ and $N_i$, followed by $S_i$ and $P_i$ if $A_i=$ 'A', for $i = 1 .. M$
Output
$M$ lines: The total productivity of the reindeer lineup after every modification
Example
Input:
5 A Dancer 5 2 A Prancer 3 8 A Vixen 10 9 R Dancer A Rudolph 3 1
Output:
0 16 34 72 80
Explanation of Sample:
After the first modification, the lineup consists of just Dancer, and so the total productivity is $0$.
After the second modification, Prancer is standing behind Dancer. Their productivity is $2 \cdot 8 = 16$.
After the third modification, we have Vixen, followed by Dancer, followed by Prancer. The productivity of Vixen and Dancer is $18$, while that of Dancer and Prancer is again $16$. Thus, the total productivity is $34$.
After the fourth modification, the lineup consists of only Vixen and Prancer, with productivity $72$.
Finally, after the fifth modification, Rudolph is behind Prancer, with this pair of reindeer contributing $8$ productivity, for a total of $80$.
hide comments
amulyagaur:
20171208 15:56:28
AC in 1 go !!! that too with the fastest solution :) 0.18s 

javesh:
20170312 17:08:38
the value of seniority and productivity as stated in ques is less than 10^6 but in one or more test case the value is more than 10^9 i.e even an integer cannot store that. Please correct that and correct me if i am wrong.


mahmud2690:
20161107 17:57:32
nice problem Last edit: 20161107 17:57:46 

Vaibhav Gosain:
20150126 19:20:44
tricky one.. :P 

Jacob Plachta:
20140116 08:18:21
There was a 1line invalidity in the data which caused a few people to get WA before, which has now been fixed. Sorry about that! 

Miguel Oliveira:
20140116 07:38:03
Hi Jacob. First of all, I would like to thank you for the problems you added. I find them challenging but approachable. I really enjoy them.


Federico LebrÃ³n:
20140116 07:38:03
200th problem :)


Edelweiss:
20140116 07:38:03
RE: That's pretty strange... Upon running your code locally, I see that it only starts producing wrong answers near the end of the largest case (after more than 90,000 operations). I don't know what kind of bug would cause that, but I'm quite confident in the data. However, your solution is far more complicated than the intended one anyway :) Last edit: 20130519 02:18:39 
Added by:  SourSpinach 
Date:  20130514 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 