Блог пользователя RubayedMunna

Map related problem.
Автор RubayedMunna, история, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

    → Ответить