What do you think of the time complexity of the following code?

multiset<int> S;
for (int i = 0, x; i < n; ++i) {
    cin >> x;
    S.insert(x);
}

for (int i = 0, x; i < n; ++i) {
    cin >> x;
    cout << S.count(x) << " ";
}

For me, I thought it should be $$$O(n \log n)$$$ until yesterday, because I thought STL implemented it by adding a field count to set, but actually this code can be as bad as $$$O(n^2)$$$, because the time complexity of S.count(x) is $$$O(\log n + k)$$$ instead of $$$O(\log n)$$$, where $$$k$$$ is the number of occurrences of x in S.

The solution is to use map in this case:

map<int, int> M;
for (int i = 0, x; i < n; ++i) {
    cin >> x;
    M[x] += 1;
}

for (int i = 0, x; i < n; ++i) {
    cin >> x;
    cout << M.count(x) ? M[x] : 0 << " ";
}

I've stepped into this trap in yesterday's educational round, my solution of D was hacked because of this. I could become master if I didn't made that mistake :(