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 case-sensitive 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!
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$
$M$ lines: The total productivity of the reindeer lineup after every modification
5 A Dancer 5 2 A Prancer 3 8 A Vixen 10 9 R Dancer A Rudolph 3 1
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$.
AC in 1 go !!! that too with the fastest solution :) 0.18s
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.
nice problemLast edit: 2016-11-07 17:57:46
tricky one.. :P
There was a 1-line invalidity in the data which caused a few people to get WA before, which has now been fixed. Sorry about that!
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.
200th problem :)
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: 2013-05-19 02:18:39