Amritapuri Regionals Problem A - Quiver - LRU - Slow insertions in map and list

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.

1 Like

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.

LRU can be implemented using arrays in order of the requests(m). So the question can be solved in O(m*logn).

1 Like

I have created a simple yet with all features for LRU cache process here

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