lucky_clover_'s blog

Question regarding the count function of std::multiset
By lucky_clover_, history, 8 hours ago, In English

Today I was attempting to hack this submission for 2061B. In this solution, the code uses s1.count(x) inside the input-reading loop. Since the time complexity of multiset's count function is $$$O(\log n + k)$$$, where $$$k$$$ is the number of occurrences of the element, the code's time complexity should become $$$O(n^2)$$$ if all elements $$$a_i$$$ are set to $$$1$$$.

However, when I submitted the hack, this code only took 109 ms. Local testing showed that it indeed results in a TLE without -O2, but runs very quickly with -O2 enabled. Does this indicate that the compiler optimizes std::multiset.count() when it is used as boolean?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think so.

Putting the code in compiler explorer, you can see the assembly generated when using count() as boolean has one less std::_Rb_tree_increment(std::_Rb_tree_node_base const*) loop.

Meanwhile the modified one that uses count(a) == 10 has

        call    std::_Rb_tree_increment(std::_Rb_tree_node_base const*)
        add     rbp, 1
        mov     rdi, rax
        cmp     r12, rax
        jne     .L71
        cmp     r13, r14
        mov     rax, r14
        cmovge  rax, r13
        cmp     rbp, 10
        cmove   r13, rax
        jmp     .L75

which seems to be the process of count() as it has a cmp rbp, 10 (comparing if the count == 10).

→ Reply