## Mock CCO '17 Day 1 P2 - Penetrating Power

View as PDF

Points: 20 (partial)
Time limit: 2.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 , yielding a match value of .
After the updates, he will choose the interval , to get a value of .
The final query can only start on positions or , therefore can only cover .

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

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

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

isnt 4 <= 4? whats the problem?

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

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

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

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.

• 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

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

Constraints have be changed to

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

Wait, C as in complex numbers?

• 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.

• 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.