GFSS Christmas Challenge P4 - Coal Counting

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Santa is known for giving presents to all the well-behaved children. However, he is also known for giving coal to the naughty ones. Santa has managed to create a system that quantifies a child's naughtiness. For each of the N children he visits, he assigns them a naughtiness value v_i.

For each year, over the course of M years, Santa's boss (his wife), gives him an integer h_j representing the naughty threshold for the j-th year. Each kid with a naughtiness value greater than or equal to the naughty threshold for that year will be given a piece of coal.

Your task is to print out the number of children who receive coal for each year on separate lines.


1 \le N,M \le 10^5

1 \le v_i,h_j \le 10^9

Subtask 1 [30%]

1 \le N,M,v_i,h_j \le 10^3

Subtask 2 [50%]

1 \le v_i,h_j, \le 10^6

Subtask 3 [20%]

No additional constraints.

Input Specification

The first line of input contains N and M.

The next line contains N space separated integers, the i-th of which representing v_i.

The next line consists of M space separated integers, the j-th of which representing h_j.

Output Specification

For each year from 1 to M, print the number of children who receive coal, each on its own line.

Sample Input

4 2
5 8 2 3
4 3

Sample Output



In year 1, Santa gives coal to children 1 and 2. In year 2, Santa gives coal to children 1, 2 and 4.


There are no comments at the moment.