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?
Input
The first line contains an integer M, the number of buildings. The second line contains M space separated integers, the heights of the buildings.
Output
Output M integers. The ith integer is the number of possible advertisements which cover the ith building partially or fully.
Example
Input: 4 2 1 4 4 Output: 5 6 12 10
Constraints
1 <= M <= 100000
1 <= h_i <= 10000
hide comments
linkret:
2018-03-16 16:11:28
VERY NICE. I LIKE |
|
bartol3141:
2018-02-05 12:41:42
Very good problem!!! Worth solving. |
|
:D:
2016-08-19 13:32:22
On output number size. Just analyze the biggest possible test case: M = 10^5, h_i = 10^4 for all i. |
|
Jose Sanchez:
2012-12-29 01:14:26
Do the output integers fits in a c++ int(4 bytes)? Last edit: 2012-12-29 01:18:12 |
|
Raghavendran Ramachandran:
2012-09-24 15:15:57
Nice problem! |
|
Daniel González:
2012-03-21 02:39:53
what's the output specification? does it have spaces?
|
|
Rajesh patidar:
2012-01-28 20:18:19
any special test case for the problem..?
|
Added by: | Varun Jalan |
Date: | 2010-07-29 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 VB.NET |
Resource: | own problem used for Indian ICPC training camp |