### 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`≤ 10

_{i}^{9}) 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`≤ 10

_{i}^{9}) 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`, for

_{i}`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)

chenjon Oct 14, 2016 - 9:42:27 pm UTC Sample Input Clarificationmagmascorpion919on Oct 15, 2016 - 12:41:49 am UTC Re: Sample Input Clarificationso the first door that opens is door 200 and the next one that opens is door 3 then door 100 then door 301.

chenjon Oct 15, 2016 - 4:21:05 pm UTC Re: Sample Input Clarification