Mock CCO '17 Problem 2 - Penetrating Power

View as PDF

Submit solution

All submissions

Best submissions

Points: 17 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

imaxblue

Problem type

imaxblue has sneaked into a meeting of $N$ ~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$ ~0~. His rifle only has a single bullet, but that bullet has a penetrating power of $K$ ~K~. This means that when he shoots, he can kill $K$ ~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$ ~Q~ queries, each in one of $2$ ~2~ forms:

0 P V: the general at position $P$ ~P~ increases by value $V$ ~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$ ~L~ and $R$ ~R~

Subtasks

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

Input Specification

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

Note that $L, R \in \mathbb C$ ~L, R \in \mathbb C~.

Sample Input

Sample Output

15
23
19

Explanation

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

Comments

0

discoverMe commented on Jan. 11, 2019, 2:35 a.m. ← edit 3 →

wait how can $K \le P$ ~K \le P~ but in the sample input $K = 4$ ~K = 4~ and in the 2nd line $P = 2$ ~P = 2~

3

magicalsoup commented on Jan. 11, 2019, 5:37 p.m. ← edit 2 →

isnt $4 \le 4$ ~4 \le 4~? whats the problem?

5

Relativity commented on Jan. 12, 2019, 3:58 a.m. ← edit 2 →

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

6

insignificant commented on April 10, 2018, 5:22 a.m. ← edit 7 →

$0 \le P \le N$ ~0 \le P \le N~

This would imply there are $N + 1$ ~N + 1~ 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 $R \ge N$ ~R \ge N~.

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

3

Cueball1234 commented on Feb. 20, 2018, 5:14 p.m. ← edit 3 →

I am really confused with this problem.

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

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

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

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

Thank you for all your help!

Edit: nvm, fixed

4

Kirito commented on May 9, 2017, 11:42 a.m. ← edit 2 →

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

15

Evan_Yu123 commented on Sept. 25, 2017, 1:19 a.m. ← edit 2 →

Wait, $\mathbb C$ ~\mathbb C~ as in complex numbers?

25

kobortor commented on May 3, 2017, 2:46 p.m. ← edit 2 →

Note that the problem setter is an amateur and did not mention that $L$ ~L~ and $R$ ~R~ could be $\ge N$ ~\ge N~.

-33

imaxblue commented on May 2, 2017, 9:54 p.m. ← edit 2 →

Problem statement was changed:
Before: "changes to $V$ ~V~"
Now: "Increases by $V$ ~V~"

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