Hello Everybody!
For "ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)" Problem C the given n is 105 and the max possible sum is 10 5 * 10 9 i.e., 1014. For the worst case, my code's complexity is: log(1014)*n. And in worst case it will be approximately 50*105 . I was expecting that my code will get Accepted easily, coz given time limit is 2.5 sec, but its exceeding time limit on 101 test case which is 100000 2 .
Isn't it possible to execute 5*106 in 2.5 sec?
Why unordered map is taking more time in comparison with map!
Thank you very much for reading!
Link to submission: 24944382
Unordered map is the problem here ...
Why???? 24945968 got AC by just changing unordered to map! Why why why???
Unordered structures are linear at worst. They use hash functions internally, so its O(1) in average but in case of multiple collisions the search takes O(n) operations. Regular map, on the other side, is O(log n) at worst.
Auto comment: topic has been updated by hmrockstar (previous revision, new revision, compare).
http://codeforces.net/blog/entry/21853 Arpa is the hero. :v
Should have seen this earlier! :'(
It's never too late (Y), great implementation: http://codeforces.net/contest/776/submission/24950229