Woburn Challenge 2015-16 Round 4

Problem J3/S1: Shootout

James Bond's latest mission is not going as planned. He's suddenly found himself at one end of a long, narrow corridor which is filled with N (1 ≤ N ≤ 200,000) of Blofeld's henchmen. The i-th henchman is standing H_i (1 ≤ H_i ≤ 10⁹) metres away from Bond along the corridor.

There are also M (0 ≤ M ≤ 200,000) doors in the corridor, all of which are initially closed, with the i-th door D_i (1 ≤ D_i ≤ 10⁹) metres away from Bond along the corridor. Of the N + M henchmen and doors, no two of them are at the same location.

The building's security system will open all of the doors in order, one after another, starting from door 1 and ending with door M. Once each door has been opened, it will stay open permanently. In order to do his best to die another day, Bond will need to quickly assess how many of the henchmen are currently in his line of fire after each door is opened. A given henchman is in Bond's line of fire if there are no closed doors between them and Bond.

Fortunately, Bond brought along his personal computer to the gunfight to help with these computations. Unfortunately, he forgot to get the floppy disk containg the program from Q! As quickly as you can, for each i from 1 to M, please help Bond determine how many of the N henchmen will be in his line of fire after the first i doors have been opened.

Subtasks

In test cases worth 3/17 of the points, N ≤ 100 and M ≤ 100.
In test cases worth another 4/17 of the points, N ≤ 200 and M ≤ 3000.
In test cases worth another 4/17 of the points, N ≤ 200 and M ≤ 40,000.

Input Format

The first line of input consists of two space-separated integers N and M.
The next N lines each consist of a single integer H_i, for i = 1..N.
The next M lines each consist of a single integer D_i, for i = 1..M.

Output Format

Output M lines with one integer per line. The i-th line of output (for i = 1..M) should consist of the number of henchmen in Bond's line of fire after i doors have been opened.

Sample Input

5 4
2
300
4
15
1000000000
200
3
100
301

Sample Output

1
3
4
5

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Apr 08, 2016
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

If there are doors at 3 and 100, as well as henchmen at 2, 4, and 15, does that mean that a henchman is before the first door? If that's the case, why would the output not be 3 3 4 5?

the order they input the door numbers is the order they open.
so the first door that opens is door 200 and the next one that opens is door 3 then door 100 then door 301.

Oh, I see. I though the doors would open in terms of their distance. Thanks!

damn, i think this question should be worth more compared to the other 7 point questions