This is a convex hull trick problem. I am building my convex hull from leaf to higher nodes. Every time I am going through all my child nodes, I am merging them together. In this solution, I am not applying light to heavy technique. Because of the increasing CHT size, I would expect my solution to get TLE on the given constraints. But for some reason, it's not getting TLE. Anyone got any proper explanation?
Problem: 932F - Escape Through Leaf
My submission: 227235272
Auto comment: topic has been updated by zzzzsust19 (previous revision, new revision, compare).
It might be that on random tests the average size of the CHT is O(log N) where N is the number of elements added at some point in time. Also you might get lucky and have the heavy nodes coveniently placed.
Yeah, but if the tree is carefully created it's possible that no line in the convex hull get's deleted. There should be test cases like that