I have solved same problem few days. TLE is happening because of log factor added as you are using Hashmap. See the editorial of this problem where the it is discussed why TLE happens. To overcome this you need to use hashing or you need to use testerās approach where he used log_5 mask which is more easy and interesting approach.

I am already using HashMap, and yes, i have referred the editorial and know how to do this using testerās idea, but i wanna know how this approach can be optimizedā¦

TLE is occuring because of the fact that you used Hashmap and every time you search for last result it occurs in log factor time. You can use array so access occurs in O(1) time but it will exceed space limit because of the constraints so you need to do āHashingā so that access of previous results occur in O(1) time, and solve collisions using Linear probing or any other technique.

Hashmap give amortised cost of O(1) but it is not guaranteed always. Rehashing occurs when size of Hahsmap exceeds cetain limit, like in vectors size of internally doubles (known as capacity of vector) when half of the vector is filled. This rehahsing is O(N) and if it occurs many times, this increases the complexity of your code. Hence, TLE. You can avoid this with only your own written hash table. (Brief part of this was also added in the editorial).

I know Hashmap rehash every time it reavh a certain size of capacity (0.75 default for Hashmap java) and its an O(N), but i havenāt ever implemented a custom hash table (not counting once when my hash table gave worse time complexity than a treemap).

Would be glad if u could help me with implementing a custom has table. I tried reading CLRS, but i guess ot was too complicated for meā¦

PS: I tried testers approach. I have understood the approach and underlying idea, but my solution is gjving TLE for subtask 1 while AC in all other subtask, except WA in 1 file.

@taran_1407 I looked into your code and honestly Iām quite confused now.
At first I thought your input method was too slow, so I just replaced it with my reader class and it was accepted: 16690821
But then I saw that your previous partially correct code uses the same input method but it works just fine for subtask 1!

You can do that, but that is not at the heart of the issue. See these 2 solutions: 16693704 and 16693711. The only difference is that in the first one the inner loop has 2 iterations and in the second one it has 3. The first takes 0.23 sec and the second takes more than 2 secs!
I really want to know the reason for this strange behaviour (ā.ā)