Company Dinner Lili works part-time in a restaurant near her campus as a waitress. One day, a boss from a company down the street decided to hold a company dinner in the restaurant she worked at. Before the dinner, the food is arranged in a sorted order A according to their type. Moments later, the manager of the restaurant confronted Lili and asks Q questions, each one asks how many foods of type Bi are there. Lili has asked you as her friend to help her count and answer as fast as possible. Format Input A single line with two integers N and Q denoting the number of food and the number of question respectively, followed by a line containing N elements denoting the type of the foods and another Q lines each containing a single integer denoting the number of occurrences of the type of food asked by the manager. Format Output Q lines each with a single integer denoting the number of occurence of Bi in A. Constraints • 1 ≤ N, Q ≤ 10^5 • 1 ≤ Ai, Bi ≤ 10^9 • Ai ≤ Aj for all 1 ≤ i ≤ j ≤ N Sample Input 1 5 5 1 1 2 2 5 1 2 3 4 5 Sample Output 1 2 2 0 0 1 Sample Input 2 3 4 2 2 2 3 2 1 10 Sample Output 2 0 3 0 0 Sir please use C language, dont use other library except , use binary search. Thx. I have code the question but when I submit it, it's time limit error, so please use binary search
Company Dinner
Lili works part-time in a restaurant near her campus as a waitress. One day, a boss from a company down the street decided to hold a company dinner in the restaurant she worked at. Before the dinner, the food is arranged in a sorted order A according to their type. Moments later, the manager of the restaurant confronted Lili and asks Q questions, each one asks how many foods of type Bi are there. Lili has asked you as her friend to help her count and answer as fast as possible.
Format Input
A single line with two integers N and Q denoting the number of food and the number of question respectively, followed by a line containing N elements denoting the type of the foods and another Q lines each containing a single integer denoting the number of occurrences of the type of food asked by the manager.
Format Output
Q lines each with a single integer denoting the number of occurence of Bi
in A.
Constraints
• 1 ≤ N, Q ≤ 10^5
• 1 ≤
• Ai ≤ Aj for all 1 ≤ i ≤ j ≤ N
Sample Input 1
5 5
1 1 2 2 5
1
2
3
4
5
Sample Output 1
2
2
0
0
1
Sample Input 2
3 4
2 2 2
3
2
1
10
Sample Output 2
0
3
0
0
Sir please use C language, dont use other library except <stdio.h>, use binary search. Thx. I have code the question but when I submit it, it's time limit error, so please use binary search.
Step by step
Solved in 2 steps
