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 :(