Sphere Online Judge

SPOJ Problem Set (classical)

3459. SkyScrapers

Problem code: CEPC08B


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 flooded. A region is a maximal set of non-flooded, adjacent skyscrapers. This term is of particular importance, as it is sufficient 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 first 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 ≤ 106), 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 h1, h2, . . . , hn
where 1 ≤ hi ≤ 109 is the height of skyscraper i. The third line of a single test case contains d numbers
tj such that 0 ≤ t1 < t2 < . . . < td−1 < td ≤ 109.

Output

For each test case output d numbers r1, r2, . . . , rd, where rj is the number of regions on day tj .

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:2008-12-06
Time limit:10s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: ERL JS NODEJS PERL 6
Resource:Central European Regional Contest 2008

hide comments
2013-08-21 12:12:20 Divanshu
O(NlogN) passes with I/O optimisations! Strict time limit!
2012-09-25 17:29:19 Galileo Figaro magnifico
Using scanf and STL sort, I get TLE.

Re: AC'ed (No I/O optimization required).


Last edit: 2012-09-26 09:26:13
2011-12-19 09:51:07 Efim
My (n log n) passed only after IO optimizations.
2010-05-06 07:05:56 Ravi Kiran
I got tle with C++ 4.0.0.8 but ac with C++ 4.3.2!
I know i could have saved the use of stl and optimised IO to get much better a time,but this is just to notify that you CAN get ac without any optimisations and using stl sort!
2009-12-20 14:57:20 Ostry
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.
2009-08-04 00:03:04 ~!(*(@*!@^&
so, dont sort :)
2009-06-03 19:47:28 Mateusz Dereniowski
Cause, the right sentence is: "I have tle cause I sort." ;)
2009-06-01 23:00:55 Przemys≥aw Derengowski
Why limits are so hard?? I have sort and tle :/

Last edit: 2009-06-02 04:53:30
2009-05-25 18:25:06 Tomasz Wasilczyk
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().
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.