The problem is the first one in this pdf - http://icpc.amrita.ac.in/2013/wp-content/uploads/2013/12/ProblemsSets2013Asia-Amritapuri.pdf .
My code http://ideone.com/wfuME8 is a implementation of LRU using unordered_map and list.
But it is very slow. I can’t even insert 10^6 elements in list in less than 3 secs.
What is the reason.
Judges at amritapuri suggested that this implementation should pass.
I think your mp.find() method is eating up lot of time.
I used priority queue & binary search to get my solution accepted. In my solution, I maintain an extra array to check whether a number is already in the queue or not. Maybe you should do something similar.
Completely true…We implemented during the competition using Linked Lists and did a binary search but still it gave TLE…I guess using priority queues was the only way to get accepted
LRU can be implemented using arrays in order of the requests(m). So the question can be solved in O(m*logn).