@author I used same approach, but my code failed to pass last test cases,here is the solution link.
https://www.codechef.com/viewsolution/7733279
I am getting TLE in DCGAME… My code is here CodeChef: Practical coding for everyone please help.Thnx in advance 
@antim_patel, This is the same problem which I and many of many friends were facing. Since your solution is quite similar to one, except the way you have calculated the frequency using stack, my suggest you to refer to my solutions CodeChef: Practical coding for everyone (50 points) and CodeChef: Practical coding for everyone (100 points).
Since I needed to reduce the constant for nlogn, I changed the quries part a bit. Since inside the queries, binary search takes (logn) time and map further takes (logn) time, the constant factor is increased. Instead of the map, the queries can be answered in O(1) using arrays. Just store the map values into an array outside the loop. Also, I removed the sort function because it was not needed as the map stores the elements in sorted order only. Sort function has a large constant factor as well.
Hope it helps.
setter and tester solution Access Denied. Please fix this
https://www.codechef.com/viewsolution/7843568
Help me, my code didnt even pass subtask 1 for some reason
Same solution but because of unnecessary computation got TLE … 
Stock Span Approach to solve m(i) array was amazing . It just does in O(n) with help of stack.
Thanks for editorial.I learned new thing today.
I also solved with same algorithm but I didn’t apply Stock Span approach.I solved it in O(NlogN) by using BST(Binary Search Tree) . It also worked and accepted. But Stock Span Approach is much much faster.
2 Likes
Would love some feedback on my code.
https://www.codechef.com/viewsolution/7861684
I was able to pass all tasks except #7 (TLE). Using randomly generated test data w/ n, m = 1,000,000 my code spends majority of time in the binary searches. I am using imported bisect_right and bisect_left from imported library. I assume that is the fasted method? Is it just a problem of python being slow? Thanks so much for any feedback.
hi,
i solved the problem using divide and conquer with binary search . I was able to get 50 points , is it able to optimize my code at any point to get better time complexity ??
here is [My Solution][1] . It passes some subtask and fails for some subtask too…can anyone
fix it??
[1]: CodeChef: Practical coding for everyone
@jeffa I also solved it using Divide and Conquer technique. I didn’t got tle. I used segment tree to get the index of the element which is maximum in the range. You should have a look at my solution if you want. Link
How are we supposed to identify that it can be solved by stock span and that we can use the formula r[i]-i*l[i]-i to find the frequencies,is there some logic to it or there are similar problems and hence the formula is known by experience?
my java implementation of the editorial.
Getting RE . Anyone can find out the problem ?
please use fast IO to get last test case/ second last test case accepted.
See the link for fast IO
Any comments/suggestions on how I can optimize my solution to pass the last subtask ? I did stack span as well as binary search and linear sum as well. But last sub task is throwing TLE !
Nice Editorial
2 Likes
This is just because there was no test data which contain all the elements in either ascending or descending order. This should not have happened.
1 Like
Your code doesn’t calculate the frequencies correctly. See editorial for help.
To identify it as the stock span problem you either need to be familiar with it or simply be able to rediscover the solution on your own (it’s not too hard really). But if you didn’t know, you can still solve it using segment trees / binary search trees, albeit at O(N log N) time.