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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


  • -1
    tiger2018  commented on March 31, 2017, 8:54 p.m.

    wut if he does not give the "I" ice cream after U do it.


  • -9
    tiger2018  commented on March 31, 2017, 8:30 p.m. edit 3

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 1
      Roynaruto  commented on March 31, 2017, 8:31 p.m.

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


      • -8
        tiger2018  commented on March 31, 2017, 8:46 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 0
          Roynaruto  commented on March 31, 2017, 8:49 p.m.

          i got strawberry ice cream :D so true :ᐋ


          • -5
            tiger2018  commented on March 31, 2017, 8:56 p.m.

            This comment is hidden due to too much negative feedback. Click here to view it.


  • 17
    jason_zhang  commented on July 9, 2016, 9:35 p.m.

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


  • 3
    Kirito  commented on July 9, 2016, 7:35 p.m.

    Java is broken again. I'm pretty sure I used more than 0 bytes.