After the Earth Queen fell, the Earth Kingdom fell into anarchy and was overrun by bandits. Luckily for the citizens of the Earth Kingdom, Kuvira the Great Uniter has brought security to the new Earth Empire and wishes to reconnect the nation by building bridges. She thinks that bridges symbolize power and wealth and will be necessary in rebuilding Republic City.
The Earth Empire consists of hills in a straight line, with the
hill having a height of
. Kuvira can build a bridge between hill
and hill
if and only if both hill
and hill
are greater or equal in height to all other hills in between them.
After losing her smartest engineer and nuking her second smartest engineer, Kuvira has been left engineer-less (and fiance-less). Seeing the opportunity for a big time promotion, you decide to help her count the number of different bridges that she can build between hills!
Hint 1
Use a stack!
Hint 2
Note that each bridge that can be made has a left and a right hill. Consider a right hill . Then you must count all left hills
with
such that you can build a bridge between hills
and
. However, observe that you do not need to consider all the hills between
. Consider hills
and
with
such that the height of
is greater than the height of
. Hill
will never be able to act as a left hill for hill
because hill
is "blocking" it. Thus, we will never have to consider hill
as a left hill for all right hills from
onward.
Input Specification
The first line will contain the integer
.
The next lines will each contain a single integer,
The heights of the hills will be given in order.
Output Specification
Print a single integer, the number of distinct bridges that can be built between 2 hills.
Sample Input
5
2
10
5
7
10
Sample Output
6
Comments
Im confused. What are you supposed to output? Why is the sample output 6? Which two hills?
Edit: Nvm, figured it out
there should be an explanation for the sample input for more clarity tbh
Any hints on how to improve my solution? Is my idea even correct in the first place?
I'd also try "A Classic problem".
edit: oops you solved it a second few i posted this comment
I don't think your solution would work even if you optimize. (Time complexity is similar to O(n^2))
Try using a stack instead for an O(n) time complexity.
Here is a similar problem that might help you solve this one: https://dmoj.ca/problem/mwc15c2p2