problem:D Most of the time i use UNORDERED MAP because it takes O(1) time, but while solving this problems, it is actually giving TLE, while on the other hand if you use ORDERED MAP which takes O(logn) time, is getting accepted.I don't know why? Can anyone please explain the reason and also how to decide in advance which to use?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Blowing up unordered_map, and how to stop getting hacked on it
This Query has been asked and answered many times on CF itself . Unordered Map is implemented using Hashtable which involves collisions if size of inputs is large and also high number of testcases which becomes very slow i.e. O(n) for find method whereas Map is implemented using Binary search trees in which find method works with O(logn) time complexity . So for small value of inputs and less testcases Use Unordered Map whereas for large number of testcases use map . On leetcode use unordered map while on codeforces use Map . Hope it answered your query .
Not true. Even with massive input sizes,
unordered_mapstill does all queries in $$$O(1)$$$ unless the input has been specifically created to cause as many hash collisions as possible. You should read this.