salt_n_ice's blog

Reason for the TLE?
By salt_n_ice, 4 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?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I did it but its still slow..(1990 ms in custom test)

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

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

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

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

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

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

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

        Works now. Thanks!

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

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

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