Vector multiple insertions showing TLE

1

hey can’t we use a vector in case of multiple insertions like when we have queries upto
200000 .
In a question i used the same thing but I am getting TLE .
queston:https://codeforces.com/problemset/problem/1066/C
submission : https://codeforces.com/contest/1066/submission/77293954

please help.

2

The time complexity of vector “insert” is O(n), and the time complexity of your code is also O(q*n).

3

please can you tell me in detail how the time complexity of insert is O(n) as every time i am inserting either at the end or at the beginning?

4

If you insert at the beginning, it will be O(n).

From C++ documentation

Because vectors use an array as their underlying storage, inserting elements in positions other than the vector end causes the container to relocate all the elements that were after position to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list)

5

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_back() and 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

6

Thanks for your explanation. Now I understood that we really don’t need an array to implement this.

7

Thanks for your explanation.