Halloween '14 P2 - Cat Girls

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 1.4s
Memory limit: 256M
Author:
FatalEagle
Problem type

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 \le p_i \le 10^9) 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 \le c_i \le 10^9) 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 Specification

The first line of input will have N (1 \le N \le 500\,000), the number of events, and W (1 \le W \le 5 \times 10^{14}), your camera's field of view, separated by a single space. The next N lines will be in one of the following forms:

  • \mathrm{A}\ p_i\ c_i

    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.

  • \mathrm{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 \le N \le 10\,000.

Output Specification

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 Output 2

The first cat girl is simply too cute for the others to compete with! Now you have 5 photos of her.

Comments


  • 3
    bariumlanthanum  commented on Jan. 27, 2023, 9:19 p.m. ← edit 2

    more images will definitely help for this problem


  • 28
    kipply  commented on May 23, 2017, 3:21 p.m.

    I need more pictures to understand the problem. Thanks!


    • 18
      r3mark  commented on May 23, 2017, 10:49 p.m. ← edited

      Here ya go


      • 3
        sunnylancoder  commented on May 24, 2017, 3:13 p.m.

        yay, now i'm motivated to do this problem


      • 8
        kipply  commented on May 24, 2017, 3:13 p.m. ← edited

        Alas, I may have these 12 points.


  • -14
    Oppenheimer  commented on Oct. 28, 2014, 8:04 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 32
      FatalEagle  commented on Nov. 1, 2014, 4:18 a.m. ← edited

      It clarifies why the cuteness value is 10\,000.


      • 19
        Kyddlygon1_9  commented on Nov. 20, 2014, 4:26 p.m.

        Exactly. The pictures were very helpful in my attempts to understand the problem.