<s> from random import randint <EOL> from bisect import bisect_right <EOL> class _Node : <EOL> def __init__ ( self , center , by_low , by_high , left , right ) : <EOL> self . center = center <EOL> self . by_low = by_low <EOL> self . by_high = by_high <EOL> self . left = left <EOL> self . right = right <EOL> def interval_tree ( intervals ) : <EOL> """<STR_LIT>""" <EOL> if intervals == [ ] : <EOL> return None <EOL> center = intervals [ len ( intervals ) // <NUM_LIT:2> ] [ <NUM_LIT:0> ] <EOL> L = [ ] <EOL> R = [ ] <EOL> C = [ ] <EOL> for I in intervals : <EOL> if I [ <NUM_LIT:1> ] <= center : <EOL> L . append ( I ) <EOL> elif center < I [ <NUM_LIT:0> ] : <EOL> R . append ( I ) <EOL> else : <EOL> C . append ( I ) <EOL> by_low = sorted ( ( I [ <NUM_LIT:0> ] , I ) for I in C ) <EOL> by_high = sorted ( ( I [ <NUM_LIT:1> ] , I ) for I in C ) <EOL> IL = interval_tree ( L ) <EOL> IR = interval_tree ( R ) <EOL> return _Node ( center , by_low , by_high , IL , IR ) <EOL> def intervals_containing ( t , p ) : <EOL> """<STR_LIT>""" <EOL> INF = float ( '<STR_LIT>' ) <EOL> if t is None : <EOL> return [ ] <EOL> if p < t . center : <EOL> retval = intervals_containing ( t . left , p ) <EOL> j = bisect_right ( t . by_low , ( p , ( INF , INF ) ) ) <EOL> for i in range ( j ) : <EOL> retval . append ( t . by_low [ i ] [ <NUM_LIT:1> ] ) <EOL> else : <EOL> retval = intervals_containing ( t . right , p ) <EOL> i = bisect_right ( t . by_high , ( p , ( INF , INF ) ) ) <EOL> for j in range ( i , len ( t . by_high ) ) : <EOL> retval . append ( t . by_high [ j ] [ <NUM_LIT:1> ] ) <EOL> return retval </s>
