DMOPC '20 Contest 2 P4 - Hungry Pigeons

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

The i-th pigeon (1 \leq i \leq N) has a beak size of b_i. Additionally, the j-th worm (1 \leq j \leq M) will have a diameter of d_j. 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 1 \leq j \leq M, what is the maximum possible satisfaction of the flock right after the j-th minute?


For all subtasks,

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq M \leq 5 \times 10^5
  • 1 \leq b_i \leq 10^9, for all 1 \leq i \leq N
  • 1 \leq d_j \leq 10^9, for all 1 \leq j \leq M
Subtask 1 [10%]

N = 2 and 1 \leq M \leq 20

Subtask 2 [10%]

1 \leq N \leq 30 and 1 \leq M \leq 300

Subtask 3 [20%]

1 \leq N \leq 2 \times 10^3 and 1 \leq M \leq 2 \times 10^5

Subtask 4 [30%]

1 \leq N \leq 2 \times 10^4 and 1 \leq M \leq 2 \times 10^5

Subtask 5 [30%]

No additional constraints.

Input Specification

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

The second line will contain N space-separated integers b_1, b_2, \ldots, b_N.

The third line will contain M space-separated integers d_1, d_2, \ldots, d_M.

Output Specification

For all 1 \leq j \leq M, output the maximum satisfaction of the flock right after the j-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 Input

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

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

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

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


There are no comments at the moment.