Queries to check if any pair exists in an array having values at most equal to the given pair | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binary_search ( vector < pair < int , int > > vec , int n , int a ) { int low , high , mid ; low = 0 ; high = n - 1 ; while ( low < high ) { mid = low + ( high - low + 1 ) / 2 ; if ( vec [ mid ] . first > a ) { high = mid - 1 ; } else if ( vec [ mid ] . first <= a ) { low = mid ; } } return low ; } void modify_vec ( vector < pair < int , int > > & v , int n ) { for ( int i = 1 ; i < n ; i ++ ) { v [ i ] . second = min ( v [ i ] . second , v [ i - 1 ] . second ) ; } } int evaluate_query ( vector < pair < int , int > > v , int n , int m1 , int m2 ) { int temp = binary_search ( v , n , m1 ) ; if ( ( v [ temp ] . first <= m1 ) && ( v [ temp ] . second <= m2 ) ) { return 1 ; } return 0 ; } void checkPairs ( vector < pair < int , int > > & v , vector < pair < int , int > > & queries ) { int n = v . size ( ) ; sort ( v . begin ( ) , v . end ( ) ) ; modify_vec ( v , n ) ; int k = queries . size ( ) ; for ( int i = 0 ; i < k ; i ++ ) { int m1 = queries [ i ] . first ; int m2 = queries [ i ] . second ; int result = evaluate_query ( v , n , m1 , m2 ) ; if ( result > 0 ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; } } int main ( ) { vector < pair < int , int > > arr = { { 3 , 5 } , { 2 , 7 } , { 2 , 3 } , { 4 , 9 } } ; vector < pair < int , int > > queries = { { 3 , 4 } , { 3 , 2 } , { 4 , 1 } , { 3 , 7 } } ; checkPairs ( arr , queries ) ; return 0 ; }