case3's blog

How to insert multiple keys in PBDS
By case3, history, 4 years ago, In English

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

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try pbds with pairs, insert{a[i],i}.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              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.

              → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply