Mock CCO '17 Day 1 P2 - Penetrating Power

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

imaxblue has sneaked into a meeting of N Amestris generals along with his sniper rifle. Unfortunately, he can't tell which one is Fuhrer King Bradley. He has assigned each general a matching value, representative of how much that general is similar to Bradley. Initially, the matching value of each general is 0. His rifle only has a single bullet, but that bullet has a penetrating power of K. This means that when he shoots, he can kill K consecutive generals in the line. imaxblue would like the sum of matching values inside this range to be high as possible.

imaxblue will have Q queries, each in one of 2 forms:

  • 0 P V : the general at position P increases by value V
  • 1 L R : imaxblue would like to know the highest possible kill he can achieve if the first(leftmost) person killed is between position L and R


For all points 0 \le K \le P \le N \le 200\,000 and 0 \le L, R, V, Q \le 200\,000
For 5 points: N, Q \le 5\,000
For additional 5 points: K=1

Input Specification

The first line contains N, K and Q.
The next Q lines contain 3 integers, representing a query.

Note that L, R \in \mathbb C.

Sample Input

8 4 8
0 2 10
0 0 4
0 6 15
1 0 5
0 3 6
0 1 3
1 0 7
1 1 2

Sample Output



imaxblue can choose to kill generals 4, 5, 6 \text{ and } 7, yielding a match value of 15.
After the updates, he will choose the interval 0, 1, 2 \text{ and } 3, to get a value of 4+3+10+6=23.
The final query can only start on positions 1 or 2, therefore can only cover 3+10+6=19.


  • 0
    discoverMe  commented on Jan. 10, 2019, 9:35 p.m. edited

    wait how can K<=P but in the sample input K=4 and in the 2nd line P=2

    • 3
      magicalsoup  commented on Jan. 11, 2019, 12:37 p.m.

      isnt 4 <= 4? whats the problem?

      • 6
        Relativity  commented on Jan. 11, 2019, 10:58 p.m.

        I believe he meant to say in the 2nd line of input, P = 2.

  • 5
    insignificant  commented on April 10, 2018, 1:22 a.m. edit 5

    {0 <= P <= N}

    This would imply there are {N + 1} positions in the array.

    It is technically correct mind you, but it would be easier if the constraints were more clear.

    If I am not mistaken there is a case where {R >= N}

    However, the sample case seems to imply that the array is 0-indexed.

  • 3
    Cueball1234  commented on Feb. 20, 2018, 12:14 p.m. edited

    I am really confused with this problem.

    For instance, how can L and R be complex numbers if they are positions?

    Is P greater than or equal than K (since the sample input does not confirm that)?

    Can K be both 0 and N, since there are only N guard positions?

    And just to double check, the guards are in a line, right?

    Thank you for all your help!

    Edit: nvm, fixed

  • 3
    Kirito  commented on May 9, 2017, 7:42 a.m. edited

    Constraints have be changed to L, R \in \mathbb C

    • 14
      Evan_Yu123  commented on Sept. 24, 2017, 9:19 p.m.

      Wait, C as in complex numbers?

  • 24
    kobortor  commented on May 3, 2017, 10:46 a.m.

    Note that the problem setter is an amateur and did not mention that L and R could be >= N.

  • -31
    imaxblue  commented on May 2, 2017, 5:54 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.