Not getting AC in hackerearth's Subarray-Function?

general
, , , , ,
1

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

2

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

3

Guys please help.

4

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

5

@vijju123

Can you look at it now.

6

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?

7

@vijju123

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

8

Can you share it on ideone etc.?

9

https://pastebin.com/samiY4JZ

10

@vijju123

you can find my solution here

11

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.

12

@meooow

Kindly help.