It's possible to use Interval Tree.. on Every node put Vector or Map or Set....
I don't know why, but when I put map I got TLe on 6-th test, but with vector + Binary search got AC:)