Halloween Kemonomimi Party 2014
Problem B: Cat Girls
This morning, you woke up and realized that some cats have turned into girls! In light of this exciting event, you have collected a large quantity of catnip to attract girls to your home (it's not as sketchy as it sounds).There, you plan to... take pictures of them while they are in a line. Don't worry, these are harmless pictures! However, your camera is quite small, and you may not be able to capture all of the cat-girls in a single photo. Your camera can only capture a contiguous subsequence of cat-girls in their line-up. Additionally, cat-girls keep showing up during the photo shoot! Even though this is a happy event, it troubles you because you always want to take the best picture you can with the available cat-girls. To complicate things further, some cat-girls want to nap so they leave the photo shoot. Fortunately, you have the cat-girls line up in a line in such a way that cat-girls only arrive and depart from the right end of the line.
Your camera's field of view is W units wide. Each cat-girl has two attributes: pi and ci. pi (1 ≤ pi ≤ 109) represents the width of the pose the cat-girl is making, in the same units as the field of view of your camera. ci (1 ≤ ci ≤ 109) represents the cuteness of the cat-girl.
The cuteness of a picture is the sum of cuteness values of the cat-girls whose full poses are captured in the picture. To satisfy your desires, you write a program to calculate the maximum cuteness you can capture in a photo after each cat-girl arrives. Initially, there are no cat-girls in the line (but don't worry, we assure you that at least one will come!).
The first line of input will have N (1 ≤ N ≤ 500000), the number of events, and W (1 ≤ W ≤ 5×1014), your camera's field of view, separated by a single space. The next N lines will be in one of the following forms:
A pi ci: A cat-girl arrives at the right side of the line with pose width pi and cuteness ci. You should output the maximum cuteness of the best picture you can take at this point in time.
D: Sadly, a cat-girl departs from the right side of the line. Don't worry, she'll surely visit again soon! You can be sure that the line will not be empty when this event happens.
At least 25% of the test cases will have 1 ≤ N ≤ 10000.
After each cat-girl's arrival, output the maximum cuteness you can take a photo of.
Sample Input 1
8 5 A 3 10 A 4 15 D A 2 9 A 1 10 A 4 15 D A 6 1000
Sample Output 1
10 15 19 19 25 19
Sample Input 2
5 100 A 100 10000 A 14 28 A 88 166 A 75 39 A 1 1000
Sample Output 2
10000 10000 10000 10000 10000
Explanation for Sample 2
The first cat girl is simply too cute for the others to compete with! Now you have 5 photos of her.
Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: Nov 04, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3