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: p_i and c_i. p_i (1 ≤ p_i ≤ 10⁹) represents the width of the pose the cat-girl is making, in the same units as the field of view of your camera. c_i (1 ≤ c_i ≤ 10⁹) 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!).

Input Format

The first line of input will have N (1 ≤ N ≤ 500000), the number of events, and W (1 ≤ W ≤ 5×10¹⁴), 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 p_i and cuteness c_i. 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.

Output Format

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.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: Nov 04, 2014
Author: FatalEagle

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I have an idea that could make my algo save some time, but before working for implementing it and seeing how much it does take to run the second part of the tests, I would like to know if there is some chance of completing it with P3.

To be honest, I have not tested this problem with Python 3, so it might be impossible. But the intended algorithm in Python 2 should be able to get at least 85/100.

Proven possible.

Oh, you did 100/100 on Python in the time limit, quantum? But I don't see your solution, possibly because the system only keeps the best time per user and you submitted with another more performing language?

On a side note, let me thank you for your concise and (imho) elegant code: even if rarely is the easier to read, it is often where I learn more while I go and check other people's work.

I have come to admire your work and I hope one day I'll be closer to your kind of knowledge with Python :)

You can view all solutions by a given user by going to their profile and clicking on the ([url=http://wcipeg.com/submissions/quantum,catgirls]15 / 15[/url]) on their profile. [url=http://wcipeg.com/submissions/src/232091]Here's a direct link to quantum's 100/100 Py3 solution.[/url]

Oh, I see, thanks. I see that I can, I mean, but of course I can't see his solution, not having solved it myself.