Not getting AC in hackerearth's Subarray-Function?

I am solving This problem from hackerearth, Unfortunately my code is not passing the two test cases, please suggest me how do I optimize it further so that I can pass all the test cases.

link to my code -> My Code

@vijju123 @likecs @taran_1407 @kauts_kanu @we7d @rajan_parmar @swetankmodi please help

Guys please help.

Sorry dear, I just saw it. I am currently all busy for long,I will look into it after long gets over, ok?


Can you look at it now.

Did you try the O({N}^{2}) approach for the problem?

The idea is to, maintain 2 priority queues, one to keep maximum element at top, other to keep minimum at top. Then try all sub arrays. Checking for first M and P elements (smallest and largest respectively) can be done in $logM $and logP time per sub array. Is it getting timed out?


That is what I did, but not getting TLE in one test case, I have attached link to my code in question.

Can you share it on ideone etc.?


you can find my solution here

Try to reduce function calls to the queue function. After doing minor optimizations of reducing such calls, 2 of the TLEs passed- I just did a work-around for your -

if (minQueue.size() < p), if (minQueue.peek() < a[j]) ,if (maxQueue.size() < m) ,if (maxQueue.peek() > a[j])

Algorithmically your approach seems correct. Reduce function calls, because its expensive even if its O(1). If my minor tweaking passed out 2 TLE out of 3, I think a bit work around is enough to get AC.


Kindly help.