Counting the number of contiguous subarrays in which the largest element of that subarray occurs only once
Разница между en1 и en2, 4 символ(ов) изменены
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.

История

 
 
 
 
Правки
 
 
  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)