MWC '15 #2 P2: Towering Towers

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.4s
Java 0.7s
Python 0.7s
Memory limit: 256M

Author:
Problem type

icicreampoph has N towers, all arranged in a straight line, with each tower having a given height H_i. When he is in a given tower, he can only see the towers which are to the left of his tower. Specifically, he can only see all consecutive towers just before his tower which do not have a greater height than his current tower. If there is a tower which is taller than the tower icicreampoph is in, he will see the tower blocking his view, but nothing past it.

icicreampoph wants to know how many towers he can see from each tower, but being lazy and not wanting to move from tower to tower, he asks you to do it for him!

Input Specification

The first line will contain an integer N (1 \leq N \leq 10^6), specifying the number of towers that icicreampoph has. The second line will contain N integers H_i (1 \leq H_i \leq 10^6), each representing the height of the i^{th} tower.

Output Specification

Output should consist of one line, with N space separated integers, the i^{th} number representing the number of towers icicreampoph can see when in the i^{th} tower.

Sample Input

5
7 4 5 4 4

Sample Output

0 1 2 1 2

Explanation of Sample Output

Arrows represent the view from each tower.


Comments


  • -11
    tiger2018  commented on April 1, 2017, 12:30 a.m. edit 3

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      Roynaruto  commented on April 1, 2017, 12:31 a.m.

      because he gives free ice cream with an i in-between


      • -11
        tiger2018  commented on April 1, 2017, 12:46 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • 0
          Roynaruto  commented on April 1, 2017, 12:49 a.m.

          i got strawberry ice cream :D so true :ᐋ


          • -7
            tiger2018  commented on April 1, 2017, 12:56 a.m.

            This comment is hidden due to too much negative feedback. Show it anyway.


  • 25
    jason_zhang  commented on July 10, 2016, 1:35 a.m.

    Icicream can use google maps so he sees all the towers duh