solution link: https://ideone.com/Dn2nQN problem link : https://codeforces.me/problemset/problem/1234/B2 Why it is giving tle at 23rd case?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
solution link: https://ideone.com/Dn2nQN problem link : https://codeforces.me/problemset/problem/1234/B2 Why it is giving tle at 23rd case?
Name |
---|
Most likely it is because you are using an unordered map. Some tests are made specifically to mess with that container. Try using a map instead.
Yeah it worked thanks ! but why was it not working with unordered map. they are faster right?
Unordered maps are faster? Can you tell me why this is so in the first place?
In map data is stored in sorted order while in unordered map it is not. operations like insert delete takes log n in map while o(1) in unordered
Are you sure operations in Unordered Map takes O(1)?
i am just a beginner. i have studied o(1) for unordered map in general. can you please tell me why map wprking instead of ump
Read this: https://en.m.wikipedia.org/wiki/Hash_table
And share this with every programmer who programs without reading the manual.
In average case its O(1) atleast read what you are sending
On average != Worst case. Read again.
yup but most of the times its O(1). i think this test case was made to avoid ump as lot of collisions is happening but still using ump is better than map right?
yup but most of the times its O(1). i think this test case was made to avoid ump as lot of collisions is happening
You just contradicted yourself and answered your original question yourself.
using ump is better than map right?
You cannot generalize stuff this way. One obvious example, how do you get the minimum/maximum element in the hash table efficiently?
ok i got your point thanks
If you want more information on unordered_map and how to make it faster: https://codeforces.me/blog/entry/62393
okk thank you!
Unordered map can have a high complexity when it is used a lot of times.
ohhkk