Queries to check if any pair exists in an array having values at most equal to the given pair | Function that performs binary search to find value less than or equal to first value of the pair ; Perform binary search ; Find the mid ; Update the high ; Else update low ; Return the low index ; Function to modify the second value of each pair ; start from index 1 ; Function to evaluate each query ; Find value less than or equal to the first value of pair ; check if we got the required pair or not ; Function to find a pair whose values is less than the given pairs in query ; Find the size of the vector ; sort the vector based on the first value ; Function Call to modify the second value of each pair ; Traverse each queries ; Evaluate each query ; Print the result ; Driver Code ; Function Call
def binary_search ( vec , n , a ) : NEW_LINE INDENT low , high , mid = 0 , 0 , 0 NEW_LINE low = 0 NEW_LINE high = n - 1 NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = low + ( high - low + 1 ) // 2 NEW_LINE if ( vec [ mid ] [ 0 ] > a ) : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT elif vec [ mid ] [ 0 ] <= a : NEW_LINE INDENT low = mid NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT def modify_vec ( v , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT v [ i ] [ 1 ] = min ( v [ i ] [ 1 ] , v [ i - 1 ] [ 1 ] ) NEW_LINE DEDENT return v NEW_LINE DEDENT def evaluate_query ( v , n , m1 , m2 ) : NEW_LINE INDENT temp = binary_search ( v , n , m1 ) NEW_LINE if ( ( v [ temp ] [ 0 ] <= m1 ) and ( v [ temp ] [ 1 ] <= m2 ) ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT def checkPairs ( v , queries ) : NEW_LINE INDENT n = len ( v ) NEW_LINE v = sorted ( v ) NEW_LINE v = modify_vec ( v , n ) NEW_LINE k = len ( queries ) NEW_LINE for i in range ( k ) : NEW_LINE INDENT m1 = queries [ i ] [ 0 ] NEW_LINE m2 = queries [ i ] [ 1 ] NEW_LINE result = evaluate_query ( v , n , m1 , m2 ) NEW_LINE if ( result > 0 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 3 , 5 ] , [ 2 , 7 ] , [ 2 , 3 ] , [ 4 , 9 ] ] NEW_LINE queries = [ [ 3 , 4 ] , [ 3 , 2 ] , [ 4 , 1 ] , [ 3 , 7 ] ] NEW_LINE checkPairs ( arr , queries ) NEW_LINE DEDENT