Hello everyone, I am trying to do Sliding Window Median problem from CSES. I have thought of multiset approach which is pretty close to one of its solutions and wrote this peice of code.
My Code
When I ran it on larger test case, it is taking this much time.
real 0m50.343s
user 0m50.003s
sys 0m0.195s
And, on the running the USACO solution, following same approach.
USACO solution
It is taking this much time.
real 0m1.396s
user 0m1.178s
sys 0m0.214s
Now, I am not able to understand that why the time taken is increasing so drastically, even though the complexities are same. I can share the complete code also if it would help. Thanks
The issue here is
low.count(a[l])
andup.count(a[l])
. The time complexity ofcount
in a multiset is I believe $$$O(log(n) + k)$$$, where $$$n$$$ is its size and $$$k$$$ is the number of elements it counted. So if the multiset entirely consists of one repeated value and you count that value, the time complexity is actually $$$O(n)$$$ and the algorithm as a whole runs in $$$O(n^2)$$$ rather than the intended $$$O(n log(n))$$$.You can replace
low.count(a[l])
withlow.find(a[l]) != low.end()
(same for up) and it should pass.Oh, I did not know that. Thanks a lot for helping sammyuri.