MWC '15 #2 P5: Watchmeblink1

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type

Mitch Jones is fighting in the WoW 3v3 Arena! There are N different abilities, numbered 1, 2, \dots, N. In order for the next ability that Mitch uses on the target T to be effective, the ability must have been cast less than K times beforehand, otherwise the ability will not be cast successfully. Mitch will cast J spells, each of which adds I casts to each ability in the range X_i, X_{i+1}, \dots, X_f for the specific target T. All abilities start with 0 casts.

Given all of the abilities Mitch casts, determine the number of abilities on each target that he will be able to cast successfully.

Input Specification

The first line will contain the integer N (1 \le N \le 10^5), the number of different abilities.

The second line will contain the integer K (1 \le K \le 10^4), the number of casts that render an ability ineffective.

The third line will contain the integer J (1 \le J \le 10^5), the number of spells that Mitch casts.

The next J lines will contain 4 space-separated integers.

These integers will be in the order: X_i, X_f, I, T:

(1 \le X_i \le X_f \le N), the range of abilities that are cast from the J^\text{th} spell.

(1 \le I \le 10^9), the number of times the above-mentioned abilities are cast.

(1 \le T \le 3), the target that the J^\text{th} cast is used on.

Output Specification

Output 3 lines: on the i^\text{th} line, output the number of abilities that Mitch will be able to successfully cast on the i^\text{th} target.

Sample Input

3 4 4 3
1 5 3 1
1 1 9 3
1 3 4 3
3 5 8 1
1 4 3 3

Sample Output


Sample Explanation

There are 5 different types of abilities, and each ability has a maximum counter value of 3. There are 6 abilities that are cast. The first one is used on target 3, adding 4 to the counter of spells 3 and 4 on that target. The second spell is used on target 1, adding 3 to the counter of spells 1 to 5, and so on. In the end, out of the 5 spells, for target 1, all spells have a counter greater than 3 and therefore, 0 spells can be cast, for target two, since no spells were cast, all 5 spells can be cast successfully, and for target 3, 1 spell has a counter less than 6.


  • 3
    Hypnova  commented on March 26, 2016, 2:31 a.m.

    Okay, everything should be fixed. Try resubmitting.

  • 1
    aurpine  commented on March 26, 2016, 2:30 a.m.

    What do I output? Is this incomplete or...?


  • 1
    Zander  commented on March 26, 2016, 1:45 a.m.

    If k is 66 then wouldnt all the cc be successful?

    • 1
      Hypnova  commented on March 26, 2016, 3:03 a.m.

      Should be good, please resubmit.

      • 3
        Zander  commented on March 26, 2016, 3:12 a.m.

        Thank you :)

    • 0
      Hypnova  commented on March 26, 2016, 2:07 a.m.

      Yeah, I've made a mistake, I will fix everything in a second.