## DMOPC '20 Contest 2 P4 - Hungry Pigeons

View as PDF

Points: 15 (partial)
Time limit: 0.5s
Memory limit: 256M

Author:
Problem type

There is a flock of hungry pigeons in Michael's backyard! Fortunately, it has started raining. Every minute, for the next minutes, one earthworm will surface from his backyard.

The -th pigeon has a beak size of . Additionally, the -th worm will have a diameter of . A pigeon can eat a worm if and only if the pigeon's beak size is strictly larger than the worm's diameter.

A pigeon's satisfaction is defined as the number of worms that the pigeon has eaten, and the flock's satisfaction is defined to be the minimum satisfaction among all pigeons in the flock. The hungry pigeons want to know: for all , what is the maximum possible satisfaction of the flock right after the -th minute?

for all

for all

#### Input Specification

The first line of input will contain two space-separated integers and .

The second line will contain space-separated integers .

The third line will contain space-separated integers .

#### Output Specification

For all , output the maximum satisfaction of the flock right after the -th minute, separated by spaces.

#### Sample Input

3 7
6 3 10
4 8 3 2 1 10 7

#### Sample Output

0 0 0 1 1 1 2

#### Explanation of Sample Output

The first three worms are too large for the second pigeon to eat, so the second pigeon must have a satisfaction of . Thus, the first three answers are .

Then, after the fourth minute, it is possible for all pigeons to have a satisfaction of (e.g. the pigeons of beak sizes , , and can eat worms of diameter , , and , respectively). Thus, the next answer is .

After the fifth minute, it is possible for any individual pigeon to eat at least worms. However, there are not enough worms for all the pigeons to have a satisfaction of at the same time, so the maximum possible satisfaction of the flow is still . The same situation occurs after the sixth minute, since no pigeon is able to eat the worm of size .

After the seventh minute, it is finally possible for the flock to have a satisfaction of .