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 \leq K \leq P \leq N \leq 200 000$ and $0 \le L, R, V, Q \le 200\,000$ $0 \leq L, R, V, Q \leq 200 000$
For $5$ $5$ points: $N, Q \le 5\,000$ $N, Q \leq 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 C$ .

Sample Input

Copy

Sample Output

Copy

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 \leq 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 \leq 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 \leq P \leq 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 \geq 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 C$

15

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

Wait, $\mathbb C$ $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$ $\geq 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.