unordered_map doesn't always work in O(1) complexity, it's O(1) for small data inputs, there are specific cases for wich the worst case is O(N) per query/update, whereas an map isn't a hash data structure, it's a binary search tree(i think the STL one uses a red-black tree), wich has a worst case complexity for query/update of O(log2(N)). if the testcase is built in a very specific way, the map can work way better in practice than the unordered_map. one way to get ac with unordered_map would be to change the hash function to something else or more simply just write your own Hash data structure it's very easy and simple to do so.