VM7WC '15 #2 Gold - Uniting the Earth Empire

View as PDF

Submit solution

All submissions

Best submissions

Points: 12

Time limit: 1.0s

Memory limit: 64M

Author:

thorthugnasty

Problem type

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 $N$ $N$ hills in a straight line, with the $i^\text{th}$ $i^{th}$ $(0 \le i < N)$ $(0 \leq i < N)$ hill having a height of $H_i$ $H_{i}$ . Kuvira can build a bridge between hill $a$ $a$ and hill $b$ $b$ $(0 \le a < b < N)$ $(0 \leq a < b < N)$ if and only if both hill $a$ $a$ and hill $b$ $b$ 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 $2$ $2$ 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 $i$ $i$ . Then you must count all left hills $j$ $j$ with $j < i$ $j < i$ such that you can build a bridge between hills $j$ $j$ and $i$ $i$ . However, observe that you do not need to consider all the hills between $0 \dots i-1$ $0 \dots i - 1$ . Consider hills $a$ $a$ and $b$ $b$ with $0 \le a < b < i$ $0 \leq a < b < i$ such that the height of $b$ $b$ is greater than the height of $a$ $a$ . Hill $a$ $a$ will never be able to act as a left hill for hill $i$ $i$ because hill $b$ $b$ is "blocking" it. Thus, we will never have to consider hill $a$ $a$ as a left hill for all right hills from $i$ $i$ onward.

Input Specification

The first line will contain the integer $N$ $N$ $(2 \le N \le 400\,000)$ $(2 \leq N \leq 400 000)$ .

The next $N$ $N$ lines will each contain a single integer, $H_i$ $H_{i}$ $(0 \le H_i < 2^{63})$ $(0 \leq H_{i} < 2^{63})$ .

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$ $2$ hills.

Sample Input

Copy

Sample Output

Copy

Comments

11

Plasmatic commented on Aug. 4, 2018, 2:16 a.m.

there should be an explanation for the sample input for more clarity tbh

2

Ninjaclasher commented on Sept. 13, 2017, 1:25 a.m.

Any hints on how to improve my solution? Is my idea even correct in the first place?

2

Xue_Alex commented on Sept. 13, 2017, 9:46 p.m. ← edited →

I'd also try "A Classic problem".

edit: oops you solved it a second few i posted this comment

2

TheZombieCloud commented on Sept. 13, 2017, 2:38 a.m. ← edited →

I don't think your solution would work even if you optimize. (Time complexity is similar to $\mathcal{O}(N^2)$ $O (N^{2})$ )

Try using a stack instead for an $\mathcal{O}(N)$ $O (N)$ time complexity.

Here is a similar problem that might help you solve this one: https://dmoj.ca/problem/mwc15c2p2

0

omaewamoushindeiru commented on Jan. 16, 2015, 11:58 p.m. ← edited →

For the sample Input/Output please.

1

awaykened commented on Jan. 17, 2015, 1:58 p.m. ← edited →

2-->10

10-->5 10-->7 10-->10

5-->7

7-->10

0

bobhob314 commented on Jan. 17, 2015, 10:59 p.m. ← edit 2 →

omaewamoushindeiru do you get it? Basically if all the stuff in the middle of the outer ones are less than or equal to both the outer ones, you can build a bridge.

0

bobhob314 commented on Jan. 16, 2015, 12:39 a.m. ← edited →

It would be really cool if we could also have other themed contests as time goes on, like a Doctor Who or Sherlock (none of that Elementary crap) contest!

:3

0

thorthugnasty commented on Jan. 18, 2015, 7:27 p.m. ← edited →

Unfortunately, those of us who make the contest are losers and have not watched any of those :(

4

FatalEagle commented on Jan. 18, 2015, 7:37 p.m. ← edited →

It's okay, my contests are almost guaranteed to be full of spoilers about ongoing anime.