COI '06 #1 Patrik

Points: 12

Time limit: 0.3s

Memory limit: 32M

Problem type

$N$ $N$ people are waiting in line to enter a concert. People get bored waiting so they turn and look for someone familiar in the line.

Two persons $A$ $A$ and $B$ $B$ standing in line can see each other if they're standing right next to each other or if no person between them is strictly taller than person $A$ $A$ or person $B$ $B$ .

Write a program that determines the number of pairs of people that can see each other.

Input Specification

The first line of input contains an integer $N$ $N$ $(1 \le N \le 500\,000)$ $(1 \leq N \leq 500 000)$ , the number of people standing in line.
Each of the following $N$ $N$ lines contains a single integer, the height of one person in nanometres.
Everyone will be shorter than $2^{31}$ $2^{31}$ nanometres.
The heights are given in the order in which people are standing in line.

Output Specification

Output the number of pairs of people that can see each other on a single line.

Sample Input

Copy

Sample Output

Copy

Comments

1

max commented on Nov. 2, 2017, 11:03 a.m. ← edit 2 →

nvm

7

Kirito commented on Nov. 2, 2017, 4:56 p.m. ← edited →

The problem is from the Croatian Olympiad in Informatics (COI), not the Croatian Open Competition in Informatics (COCI).

8

aeternalis1 commented on Aug. 31, 2017, 2:40 a.m. ← edit 3 →

Is there a point inconsistency with https://dmoj.ca/problem/vmss7wc15c2p3? My solution AC's the latter but TLE's this one.

2

ACCount_Nine38 commented on July 29, 2019, 5:32 p.m.

Java stack is too slow for this problem. Change your stack into an array which will resolve the TLE.