Recently, I tried to solve the problem: Meteors
It is a well-known problem that is usually solved using Parallel Binary Search.
However, before learning about that technique, I attempted to solve it in my own way. Surprisingly, my solution somehow passed within the time limit, even though I expected it to get TLE based on my complexity estimation.
At first, I estimated my code’s complexity as: (n + m) * log(m) * log(q)^2
The part that confuses me is the binary search: inside it, I loop over a node vector of size roughly log(m). At the same time, the total size of all vectors could be around q * log(m), as far as I understand.
Does the segment tree structure somehow reduce the number of iterations or the effective number of values processed, or am I misunderstanding the actual complexity?
For context, the input function is implemented as an iterative segment tree. Each query stores a prefix sum over a range, and the crn_node function is used to collect all the relevant node indices along the path for a given position p.
To my understanding, I would have needed to remove at least one or more log factors from the complexity just to pass the time limits.
If there’s some good reason why it passed, then this kind of trick could be really useful for other problems as well. I’d love to understand it properly and learn how and why. Any insights or guidance would be greatly appreciated!
