Counting the number of contiguous subarrays in which the largest element of that subarray occurs only once

Правка en1, от Nams, 2015-09-27 17:45:43

Hello all,

This is my first blog entry on Codeforces. So please forgive me if I am not following any regulation. I recently came across a question.Its statement goes like this:

Given an array A1,A2...AN. We are asked to count the number of contiguous subarrays Ai,Ai+1...Aj such that 1≤i≤j≤N and the largest element of that subarray occurs only once in that subarray.

For example: If N=3 A[3]={1 2 3} => Ans=6 If N=4 A[4]={2 2 1 2} => Ans=6

Constraint: 1<=N<=10^5 and 1<=A[i]<=10^5

I have the Naive approach which works in O(n^2) but as evident from constraints it would give TLE. So please help to optimize the solution. Thanks.

Теги array, tle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Nams 2015-09-27 17:46:42 4 Tiny change: '=> Ans=6\nIf N=4\nA[' -> '=> Ans=6\n|| If N=4\nA['
en1 Английский Nams 2015-09-27 17:45:43 758 Initial revision (published)