silversRayleigh's blog

By silversRayleigh, history, 5 years ago, In English

I was trying to solve the problem Jail Destruction. I used square root decomposition approach. I divided whole array in sqrt(N) blocks and sorted each block w.r.t height and maintained a counter for each block which contains the value by which whole block has been subtracted. To process query of 2nd type, I iteratively changed the values of start/end blocks and processed them again while increased counter value for intermediate blocks. Similarly for query of first type, I calculated value of start/end blocks and for intermediate blocks used binary search as well as suffix sum.

While submitting the solution I got WA. Can anyone please let me know if there is anything wrong with the idea or help me find bug in my code. I have tried multiple time but to no avail.


Link to Problem : Link to solution :