You can use a deque, but that doesn’t seem to be the correct approach.
In your code, Both find and insertion at the beginning is O(n).
You can use imaginary 2 pointers to solve this.
We first need a map, that lets us know the index of any id in O(1) time.
vector<int> map(MAXID+1);Should suffice.
Now imagine two pointers one at lidx=0, and the other at ridx=1. It’s NOT pointing to any real array. We have our imaginary array that supports both
push_front() in O(1) time. Let’s call that arr
Any index i, that satisfies lidx<i<ridx is a valid index.
When we get a query to push book with ID x to the left, We push it to the front, so arr[lidx]=x. We update our map with
map[x]=lidx, and then decrease lidx.
When we get a query to push book with ID x to the right, We push it back, so arr[ridx]=x. We update our map with
map[x]=ridx, and then increase ridx.
When we get a query to find distance of ID x, we know ridx, so distance from the right is ridx-map[x]-1, The distance from the left is map[x]-lidx-1.
Over here, you notice, That we don’t really need the array itself, so we can consider it to be imaginary.
My submission : Submission #77311965 - Codeforces