RubayedMunna's blog

By RubayedMunna, history, 2 years ago, In English

I got a problem whenever I was solving Atcoder contest.

I have an array. I want to store index of every occurrences of every elements of the array so that whenever someone gives me two number x and k, I can show him/her the index of k th occurrence of x.

To do this, I used a map. I used the key value of map as elements of the given array and for mapped value I used a vector so that I can push back the occurrences of the elements to the vector(mapped value).

Now, the problem is I don't know how to push back indexes to the map of vector. I also faced problem whenever I tried to find k th occurrence of the element x.

If I'm wrong, please correct me.

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Well, if for example if you have declared you map as:

map<int, vector<int>> m;

when you access an element x, m[x] basically returns a reference to the vector asociated to the key x. So consequently, everything you can do to a vector you can do to m[x]. Examples:

m[x].size();
m[x].push_back(i); // the answer to your initial question
sort(m[x].begin(), m[x].end());
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also here's my submission in case it helps:

    C. The Kth Time Query — my solution

    (I used unordered_map since it's a bit faster but it works the same with map)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly!

    And to get k-th element you can use:

    m[x][k]
    

    Or more precisly (because in C++ first element is 0):

    m[x][k-1]
    

    To check if m[x] have at least k element you should use:

    m[x].size() >= k
    

    And to check if x is the map, you can use:

    m.count(x) > 0
    

    (You can use m[x].size() > 0 but this would create a new element in map m)