Let's take a look at my 2 submissions for problem 681C
20333485 — TLE, don't use ostringstream
20333517 — AC, use ostringstream
Briefly, the answer of the problem is a string has 1e6 lines, each line has maximum 20 characters.
In the first submission, I stored the answer in string res, then I sum "res = res + line". Finally I printed "cout << res" and got TLE
But in the second submission, I stored the answer in sout object ( an ostringstream), sum "sout << line", and printed "cout << sout.str()" and got AC ( even 4 times faster than the first submission)
I don't understand the reason behind this. Anyone could explain it ?
Thank you in advance
In the code of the first submission, try changing
res = res + linebyres += line.And to make it even faster, add
in the beginning.
As olenihc pointed out,
res = res + lineworks way slower thanres += line.The reason behind this is that when you are trying to assign
res + linevalue tores, this takes O(N + M) time where N is length of res and M is length of line.In total these operations might take
O(Q^2 * L)time (where L is length of line in your case and Q is how many times did you call this operator)This is actually pretty much, you can see 20342784 this submission, where I'm adding "1" to temporary string many times with copying, and as you can see this submission gets TL.