Hello. This is a CSES problem: Sliding Median. My logic is to have a sorted structure which can store multiple keys in sorted order and then I'll take middle of that data structure and then remove by index and do it again. So my time complexity analysis is: O(nlog(n))
I thought of PBDS. Inserting and sorting is find but how to have multiple keys. Using less_equals is not working for me. Is there anything I can do with PBDS or I need to think of some other logic.
My Code with PBDS I have printed the set so to analyze what was going on.
PS: Please don't tell me the logic just help me with the PBDS and this logic otherwise I'll think about something else then :)
Try pbds with pairs, insert{a[i],i}.
Thank you I got AC. Can you please tell me why less_equal doesn't work or speaking it like this, what is less_equal in pbds
I think you are asking how to find number of values less than equal to some x in pbds with pairs. s.order_of_key({x, n+1}) where n=number of elements in array. Or you can use any big value instead of n+1. s=name of pbds you initialized.
Brother I was not asking this but thank you. I am saying that in the declaration of ordered_set I used less_equal instead of less. With this my set containing duplicate values and behaving like multi-set but I am not able to do the operation erase on it. Why?
In multiset we use s.erase(s.find(key)) to erase one occurrence of a value. In pbds i don't think there is such operation.
Then what erase of pbds do?
What generally erase does !!!!!
It's not doing that :))) It's just there erasing nothing but my hopes
Anyways hope is a good thing.
You are not just unable to do
erase, you're unable to use pretty much anything else, because usingless_equalis UB. God, please don't use it, use a normal solution like what palsoumyadeep suggested.Why are you so pissed off with less_equal? But the thing is, why it is the upper_bound? If I have {1,2,5,5,5,6,9} 0 based indexing, What is s.find(5) ? Just explain me this if you have a bit of time :)
Because the standard requires the comparator to have transitivity of less-then, greater-than and equal-to relations, along with law of trichotomy, which does not hold for $$$\le$$$ operator, which is precisely the reason why
less_equalandupper_boundget swapped, andfindanderasestop working.The mistake you doing in your code is that you are erasing elements with value instead of iterator. Use find to first find the value and then use erase on the found iterator.
erase also takes up a value. So if i am giving it a value directly it gives me s.end() iterator on find as I checked now. So order_by_key works and not erase(find) in using less_equal. Can you explain me why :)
No idea bro.