SpongeBobSquarePants's blog

By SpongeBobSquarePants, history, 6 weeks ago,

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 :)

• -9

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by SpongeBobSquarePants (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 Try pbds with pairs, insert{a[i],i}.
•  » » 6 weeks ago, # ^ |   0 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
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 6 weeks ago, # ^ |   0 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?
•  » » » » » 6 weeks ago, # ^ |   0 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.
•  » » » » » » 6 weeks ago, # ^ |   0 Then what erase of pbds do?
•  » » » » » » » 6 weeks ago, # ^ |   0 What generally erase does !!!!!
•  » » » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 It's not doing that :))) It's just there erasing nothing but my hopes
•  » » » » » » » » » 6 weeks ago, # ^ |   0 Anyways hope is a good thing.
•  » » » » » 6 weeks ago, # ^ |   0 You are not just unable to do erase, you're unable to use pretty much anything else, because using less_equal is UB. God, please don't use it, use a normal solution like what palsoumyadeep suggested.
•  » » » » » » 6 weeks ago, # ^ |   0 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 :)
•  » » » » » » » 6 weeks ago, # ^ |   +8 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_equal and upper_bound get swapped, and find and erase stop working.
 » 6 weeks ago, # | ← Rev. 2 →   0 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. My code// C++ Program to implement the // above approach #include #include using namespace std; using namespace __gnu_pbds; // Policy based data structure typedef tree, rb_tree_tag, tree_order_statistics_node_update> indexed_set; #define ll long long int #define pii pair #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define vi vector #define vii vector #define all(x) x.begin(),x.end() #define eb emplace_back #define yes cout<<"YES"<, greater> #define maxpq priority_queue void sout(){ cout< void sout(T var1,Types... var2){ cout<>n>>k; int a[n]; rep(i,0,n){ cin>>a[i]; } rep(i,0,k){ s.insert(a[i]); } if(k%2==1){ cout<<(*s.find_by_order(k/2))<<" "; } else{ cout<<(*s.find_by_order(k/2-1))<<" "; } rep(i,k,n){ s.erase(s.find_by_order(s.order_of_key(a[i-k]))); s.insert(a[i]); if(k%2==1){ cout<<(*s.find_by_order(k/2))<<" "; } else{ cout<<(*s.find_by_order(k/2-1))<<" "; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; // cin>>t; t=1; while(t--){ solve(); } } 
•  » » 6 weeks ago, # ^ |   0 Thanks a lot this makes sense.
•  » » 6 weeks ago, # ^ |   0 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 :)
•  » » » 6 weeks ago, # ^ |   0 No idea bro.