Haven't examined the whole code, but one issue that jumps out is that you use lower_bound for the set wrongly. The way you use it, it works slower than $$$O(\log n)$$$ (either $$$O(n)$$$ or $$$O(n \log n)$$$, don't remember exactly). When you use lower_bound or upper_bound for a set-like structure, you should call it as a member function.