CEPC08B  SkyScrapers
In a seaside village, there is an avenue of skyscrapers. Each skyscrapers is 100m wide and has certain height. Due to very high price of parcels, any two consecutive skyscrapers are adjacent. The avenue lies close to the beach so the street is exactly at the sea level. Unfortunately, this year, due to the global warming, the sea level started to increase by one meter each day. If the skyscraper height is no greater than the current sea level, it is considered ﬂooded. A region is a maximal set of nonﬂooded, adjacent skyscrapers. This term is of particular importance, as it is suﬃcient to deliver goods (like current, carrots or cabbages) to any single skyscraper in each region. Hence, the city major wants to know how many regions there will be in the hard days that come. An example of an avenue with 5 skyscrapers after 2 days is given below.
Input
The input contains several test cases. The ﬁrst line contains an
integer t
(t ≤ 15) denoting the number
of test cases. Then t
test cases follow. Each of them begins with a line containing two
numbers n
and
d (1 ≤ n, d
≤ 10^{6}), n
is the number of skyscrapers and d
is the number of days which the major wants
to query. Skyscrapers are numbered from left to right. The next line
contains n integers h_{1}, h_{2},
. . . , h_{n}
where 1 ≤ h_{i} ≤ 10^{9} is the
height of skyscraper i.
The third line of a single test case contains d numbers
t_{j} such that 0 ≤ t_{1}
< t_{2} < . . . < t_{d−1}
< t_{d} ≤ 10^{9}.
Output
For each test case output d numbers r_{1}, r_{2}, . . . , r_{d}, where r_{j} is the number of regions on day t_{j} .
Example
Input: 2 3 3 1 2 3 1 2 3 5 3 1 3 5 1 3 0 2 4 Output: 1 1 0 1 2 1
Added by:  Robert Rychcicki 
Date:  20081206 
Time limit:  1.160s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: ERL JS NODEJS PERL 6 VB.net 
Resource:  Central European Regional Contest 2008 
hide comments
Divanshu:
20130821 12:12:20
O(NlogN) passes with I/O optimisations! Strict time limit! 

Raghavendran Ramachandran:
20120925 17:29:19
Using scanf and STL sort, I get TLE.


Efim:
20111219 09:51:07
My (n log n) passed only after IO optimizations. 

Ravi Kiran:
20100506 07:05:56
I got tle with C++ 4.0.0.8 but ac with C++ 4.3.2!


Ostry:
20091220 14:57:20
I'm having TLE all the time. Even when removing all my code (only data input functions remaining). There must be sth wrong with their input. 

~!(*(@*!@^&:
20090804 00:03:04
so, dont sort :) 

Mateusz Dereniowski:
20090603 19:47:28
Cause, the right sentence is: "I have tle cause I sort." ;) 

Przemys³aw Derengowski:
20090601 23:00:55
Why limits are so hard?? I have sort and tle :/ Last edit: 20090602 04:53:30 

Tomasz Wasilczyk:
20090525 18:25:06
Limits are very stict: my first solution, with my own input reading and using qsort() had TLE. It get finally passed after replacing qsort() with sort(). 