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.
↵
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.
