## Mock CCO '17 Problem 2 - Penetrating Power

View as PDF

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

Author:
Problem type

imaxblue has sneaked into a meeting of 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 . His rifle only has a single bullet, but that bullet has a penetrating power of . This means that when he shoots, he can kill consecutive generals in the line. imaxblue would like the sum of matching values inside this range to be high as possible.

imaxblue will have queries, each in one of forms:

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

For all points: and
For points:

#### Input Specification

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

Note that .

#### 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

15
23
19

#### Explanation

imaxblue can choose to kill generals , , and , yielding a match value of .
After the updates, he will choose the interval , , and , to get a value of .
The final query can only start on positions or , therefore can only cover .

• commented on Jan. 11, 2019, 2:35 a.m. edit 3

wait how can but in the sample input and in the 2nd line

• commented on Jan. 11, 2019, 5:37 p.m. edit 2

isnt ? whats the problem?

• commented on Jan. 12, 2019, 3:58 a.m. edit 2

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

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

This would imply there are positions in the array.

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

https://dmoj.ca/submission/862887

If I am not mistaken there is a case where .

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

• commented on Feb. 20, 2018, 5:14 p.m. edit 3

I am really confused with this problem.

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

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

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

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

Thank you for all your help!

Edit: nvm, fixed

• commented on May 9, 2017, 11:42 a.m. edit 2

Constraints have be changed to

• commented on Sept. 25, 2017, 1:19 a.m. edit 2

Wait, as in complex numbers?

• commented on May 3, 2017, 2:46 p.m. edit 2

Note that the problem setter is an amateur and did not mention that and could be .

• commented on May 2, 2017, 9:54 p.m. edit 2

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