silversRayleigh's blog

By silversRayleigh, history, 5 weeks 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.

TIA.

Link to Problem : https://codeforces.com/gym/102307/problem/J Link to solution : https://codeforces.com/gym/102307/submission/60750946

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it