Queries to check if sweets of given type can be eaten on given day or not | C ++ program for the above approach ; Function to find queries to check if a sweet of given type can be eaten on a given day or not ; Stores pairs { priority , quantity } of each sweet - type ; Sorting the order of sweets in decreasing order of their priority ; Stores the window { min_days , max_days } for each sweet - type ; Variables to calculate the windows ; Traverse the array ; Calculating maximum and minimum number of days required to complete the sweets of the current type ; Creating the window and storing it ; Traversing the queries ; x : Type of sweet , y : Day ; Find the window for the sweet of type x ; If the given day lies within the window ; Driver Code ; Quantites of sweets of each type ; Priorites of each type sweet ; Maximum sweet of one type that can be eaten on a day ; Queries ; Calculating number of types
#include <bits/stdc++.h> NEW_LINE using namespace std ; void sweetTypeOnGivenDay ( int a [ ] , int b [ ] , int n , int k , vector < pair < int , int > > & q ) { vector < pair < int , pair < int , int > > > v ; for ( int i = 0 ; i < n ; i ++ ) v . push_back ( { b [ i ] , { a [ i ] , i + 1 } } ) ; sort ( v . begin ( ) , v . end ( ) , greater < pair < int , pair < int , int > > > ( ) ) ; map < int , pair < int , int > > mp ; int lowerbound = 0 , upperbound = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int maxi_days = v [ i ] . second . first ; int mini_days = v [ i ] . second . first / k ; if ( v [ i ] . second . first % k != 0 ) mini_days ++ ; upperbound += maxi_days ; mp [ v [ i ] . second . second ] = { lowerbound , upperbound } ; lowerbound += mini_days ; } for ( int i = 0 ; i < q . size ( ) ; i ++ ) { int x = q [ i ] . first , y = q [ i ] . second ; int e = mp [ x ] . first ; int f = mp [ x ] . second ; if ( y >= e && y <= f ) cout << " Yes " << " ▁ " ; else cout << " No " << " ▁ " ; } } int main ( ) { int A [ ] = { 6 , 3 , 7 , 5 , 2 } ; int B [ ] = { 1 , 2 , 3 , 4 , 5 } ; int K = 3 ; vector < pair < int , int > > Queries = { { 4 , 4 } , { 3 , 16 } , { 2 , 7 } } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; sweetTypeOnGivenDay ( A , B , n , K , Queries ) ; }