In 1718C - Tonya and Burenka-179 I implemented a solution with intended complexity (which was O(n*log(n)*PrimeFactorCount(n))), which need a multiset to update the possible answer between queries, and answer the max element of the multiset for each query. But since there's no multiset in java, I had to simulate a multiset by a TreeMap, which caused TLE (my submission:188008030)
I looked at other java solution for this problem and no one got AC. Is this problem unsolvable for java or there's better implementation for multiset?
Update: I rewrote my code and implemented the same algorithm using array, without HashMap and TreeMap. Now I've got AC and become the first who solved this problem in java. My new submission:188028411
Perhaps the constant factor of HashMap, TreeMap, ArrayList... in java is too large for auto-(un)boxing. It's better to avoid use generics for primitive types if possible.
This post might be helpful: https://codeforces.me/blog/entry/62393
They can find a way to hack your hash and make it O(N^2)
Auto comment: topic has been updated by YocyCraft (previous revision, new revision, compare).
It's frustrating to come up with the correct idea, implement the solution with intended time complexity, and get TLE for large time constant factor caused by the design fault of the programming language. In such case I must optimize the algorithm further than intended，and focus on every details which may increase the time cost.
In this case it's not only because of the language. I've gotten TLE using C++ for using map instead of vector + sort + binary search a couple of times, including possibly in ICPC WF.