Passing Temple Queues using treaps

help
#1

I have passed Temple Queues on SPOJ in 1370ms, but I’m curious if it can be optimized so much as to pass the same question on Codechef in less than 400ms.

SPOJ problem link: SPOJ.com - Problem TEMPLEQ
My code link: SPOJ TEMPLE QUEUE 1370ms - Pastebin.com
CodeChef problem link: Contest Page | CodeChef

I have already spent too much time optimizing but can’t get any more improvement than this. Please give optimization tips/tricks :slight_smile:

[I know the solution using BIT, I just really want to optimize my treap implementation as much as possible]

#2

1370ms is not running time of a single test case, it is the sum of running time of all test cases.