salt_n_ice's blog

By salt_n_ice, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

        Works now. Thanks!

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

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

        • »
          »
          »
          »
          »
          4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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 ?

            • »
              »
              »
              »
              »
              »
              »
              4 weeks 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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks 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.