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

nicely explained :)