salt_n_ice's blog

Reason for the TLE?
By salt_n_ice, 6 years ago, In English

link

My solution

As the constraint is m*n<=10^6, this solution should work under 1 second but it's taking about 1871 ms in one of the TLE'd test case. Why could this be happening?

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

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

add after declaring v.reserve(n*m);

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

It is RTE, try "resize" instead of "reserve".

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

    I tried both, still it takes around 1880 ms..

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

      Now got it. Don't use "endl", use "\n" instead.

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

        Works now. Thanks!

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

        using "\n" instead makes that much of a difference ??

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

          endl is write a newline and flush the stream. flush the stream each line take lot of time.

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

          From the Competitive Programmer's Handbook, which I'm reading now: "Note that the newline "\n" works faster than endl, because endl always causes a flush operation."

          If there are many lines in the output, then all these flushes may kill performance.

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

            i see.. but my hands are set on endl.. we can always #define endl "\n" right ?

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

              Until you face an interactive problem -> where you would need endl to flush the stream

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, hide # ^ |
                 
                Vote: I like it +3 Vote: I do not like it

                For interactive problems, '\n' will also work because a read from cin forces to flush cout, unless cin.tie(0) is used:

                cin is tied to the standard output stream cout (see ios::tie), which indicates that cout's buffer is flushed (see ostream::flush) before each i/o operation performed on cin.

                For non-interactive problems cin.tie(0) should be used, to prevent the flush operations, in case there are some interleaving input and output operations.

                → Reply