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 Hi (1 ≤ Hi ≤ 109) 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 Di (1 ≤ Di ≤ 109) 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.
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.
The first line of input consists of two space-separated integers N and M.
The next N lines each consist of a single integer Hi, for i = 1..N.
The next M lines each consist of a single integer Di, for i = 1..M.
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.
5 4 2 300 4 15 1000000000 200 3 100 301
1 3 4 5
Point Value: 7 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Apr 08, 2016
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3