__abs's blog

By __abs, history, 23 months ago, In English

Question. I understand how to solve this using Segment Trees.

I saw this solution by pikmike.

Copied here

Can someone explain how this works?

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

»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Divide N hotels into groups of size 450. Just iterate from 1 to N/450 to find first group with required rooms while maintaining group max after each query.