SomeRandomGuy's blog

Tle on powerfull array
By SomeRandomGuy, history, 9 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?
»
9 years ago, # |
  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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I updated my code, but I am getting Tle 50.

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

      I got it accepted 12479877 by changing %lld to %I64d(as Codeforces recomends) and changing comporator a bit.

      P.S Sometimes adding some constants to sqrt(n) can make your solution work faster.

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

        Thank you

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

        "Sometimes adding some constants to sqrt(n) can make your solution work faster".. this statement works for me to get accepted :-)

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

    Thanks, but why?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        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
      • »
        »
        »
        »
        9 years ago, # ^ |
          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
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            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
»
6 years ago, # |
  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