Help in Square root decomposition approach for the JAIL DESTRUCTION

Revision en1, by silversRayleigh, 2019-09-18 09:29:46

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 :

Tags #sqrt decomposition, #gym


  Rev. Lang. By When Δ Comment
en1 English silversRayleigh 2019-09-18 09:29:46 989 Initial revision (published)