BUILDING - Buildings
A certain city has M buildings, all having a width of 1. The ith building has height h_i units. The outline of the city can be seen by everyone passing along, and you wish to place an advertisement in front. You want the advertisement to be totally contained within the boundary defined by the outline of the city. The advertisement should be rectangular in shape, and its base should be at ground level. Also, it should have an integral height and its vertical edges should coincide with the vertical edges of the buildings. Now you wonder, for each building x, how many ways are there to place an advertisement such that it hides (fully or partially) building x ?
The first line contains an integer M, the number of buildings. The second line contains M space seperated integers, the heights of the buildings.
Output M integers. The ith integer is the number of possible advertisements which cover the ith building partially or fully.
Sample Input :
2 1 4 4
Sample Outout :
5 6 12 10
1 <= M <= 100000
1 <= h_i <= 10000
Very good problem!!! Worth solving.
On output number size. Just analyze the biggest possible test case: M = 10^5, h_i = 10^4 for all i.
Do the output integers fits in a c++ int(4 bytes)?Last edit: 2012-12-29 01:18:12
what's the output specification? does it have spaces?
any special test case for the problem..?