SomeRandomGuy's blog

Tle on powerfull array
By SomeRandomGuy, history, 11 years ago, In Russian

86D - Powerful array . I am trying to solve this problem, but I am getting TLE 50. Can anybody help me. My solution 12479619
UPD: Got AC

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

cnt can be simple array, not map. It will delete O(log(n)) from complexity

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
sort(q + 1, q + 1 + m, Comp);

replace function with function object (i.e. struct with overloaded operator()) or with lambda — this also leads to significant speedup

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

    Thanks, but why?

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

      because compiler typically cannot inline function passed by pointer. In many cases sorting with function pointer is 2x-3x times slower than sorting with lambda

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

        Do you have a source on that? I think you may be confusing things with qsort (which may be slower than sort, but that's because it's not templated, not because of function pointer).

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

          Effective C++, 3rd Ed., item 30. And I didn't tested qsort, only std::sort with different comparators. I even tried to compare assembler outputs here — https://goo.gl/5D4vXz. IMO all results are evident

          → Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I optimized my code to be able to use it with cout and cin, here is my code 52278174

→ Reply