I can't solve this problem using python. I tried many variations of my code but all of them give TLE for 2 test cases. In C++, this problem can be solved using multiset, I tried using dict, collections.Counter, list in python but all of them give TLE. I used stdin and stdout to read the input and output. The time limit is 1 sec and 2 test cases with n = 2⋅10^5, m = 2⋅10^5 pass while the other two don't. I tried searching for solutions but the solutions provided also gave TLE in both cpython and pypy.
If two test cases with n = 2⋅10^5, m = 2⋅10^5 pass with time 0.2 sec maximum then how slow is my solution for the other test cases with similar values?
These two codes gave the best and similar results. First, Second.
UPD: Solved.
I guess this not possible to do in python(At least for me). The data structure being used here is ordered multiset(in c++) as you mentioned already. Even I have tried what you mentioned(dictionaries, Counters, sets, etc) but nothing works. So in the end I implemented my own self-balancing tree in python, to perform insertion deletion and searching in O(log(n)) time but even that didn't work so I gave up(because I know c++ so didn't bother to waste anymore time). Also here is this blog where you can see what pllk (problem setter of cses and author of this nice book) has to say about Time Limits and language preference when asked by a user.
PS: If someone has done this problem in python please post your code. I really want to know how to do this in python.
Once you solve a problem in CSES, a new
Hackingtab appears. You can use this to see others' solutions. Because of the no-editorial nature of CSES I'm hesitant to actually post some random person's Python solution, but once you solve the problem you should be able to see it yourself.