PROBLEM LINK:Author and Editorialist: Soumik Sarkar DIFFICULTY:EASY PREREQUISITES:Sorted set/Priority queue/Heap, Difference array PROBLEM:There is an array $Z$ of size $N$ denoting the health of $N$ zombies. There also $M$ types of beams of the form $(L, R, K)$ where $K$ denotes the number of times the beam can be used to decrease every element in $Z[L..R]$ by $1$. Find the minimum number of beam drops needed to reduce all elements in $Z$ to $0$ or determine if it is impossible. EXPLANATION:Consider the first zombie $Z[1]$. This zombie can only be affected by beams whose $L = 1$. Let's gather all such beams into a set $U$. If we want to reduce $Z[1]$ to $0$, we have to drop some beams from $U$. Of course we should drop the number of beams exactly equal to its health and not waste any beams. The question is.. which beams should we drop? After killing the first zombie let us move to $Z[2]$. Of course $Z[2]$ may already have been reduced to $0$ after being affected by the beams that we used on $Z[1]$, but let us assume it is still nonzero. Now we are faced with a similar situation as before. Only those beams with $L \le 2$ can affect $Z[2]$. But all beams with $L = 1$ were added to $U$, and some of them are even already used. So we must add all the beams that have $L=2$ to the leftover beams in $U$, and make greedy choices again to reduce $Z[2]$. Generalizing, the solution involves maintaining an active set of beams $U$. At any index $i$, all beams that can affect $i$, ie. beams that have $L \le i$, are either in set $U$ or have been used up. To kill zombie $i$, only as many beams as required are used, the beams with largest $R$ being used first. The process is carried out for $i = 1$ to $N$. The algorithm can be described as follows:
The above strategy is optimal, but how can we implement it efficiently? The two procedures that are nontrivial are retrieving the update with largest $R$ from $U$ and applying decrement operations on a range $Z[L..R]$. The complexity of the solution is $\mathcal{O}((N + M)\log M)$. AUTHOR'S AND TESTER'S SOLUTION:Author's solution can be found here asked 16 Apr, 00:39

Didn't understand following line from the editorial: Note that the updates to be applied only affect elements to the right of the current index, so we can maintain the prefix sum in a variable and just modify D[R + 1]as required. Can someone please elaborate? I am coding in Python3. Thanks, Shubham answered 04 Aug, 17:29

nicely explained :)
Shakti Billi's editorials are simply <3 :D
I couldn't find the option to comment so posted as answer.
Didn't understand the line: Note that the updates to be applied only affect elements to the right of the current index, so we can maintain the prefix sum in a variable and just modify D[R + 1] as required.
Can someone please elaborate? Thanks, Shubham
I am unfamiliar with C++ and Java. So I am unable to understand the solutions of the author and the tester properly. I am coding in Python. Can somebody please help me with my request above?
Hello @deathraider162, the sum of all damage that affects the zombie at current index is maintained in the variable
dmg
. This value is increased when a beam is dropped and at every index it is reduced by the sum of damage of all the dropped beams whose end point is the previous index. You can try to follow how it is being used in my equivalent Python solution: 19483987