What? I fast scaned your solution, it looks like a O(NM) algorithm? You mean the “stack” for another M? It seems that all number will be in/out the stack only once. Therefore O(NM) in total?
No, there are three nested for-loops clearly visible in inline void racunajsol()
Thanks mate …much appreciated
add link please
you used cout in C++ and printf in C which is much faster than cout …
can anyone tell the complexity of my C sol link given above. Is it according to the editorial or not?
my pleasure to help you
wait, I see a totally different solution than what I read before… let me have a look
okay, you are right. thanks to the weak test cases and relax time limit.
Indeed, I am still waiting for Suraj to give me the links too…
Hm? fropen
is not commented in code with TLE you linked!
Why not use some of the accepted solutions and check it yourself? The largest input file size is 6957085 bytes, so your test case is not included.
It is definitely no problem to handle such amount of data in C and C++ (based on the accepted solutions, even 10 times as big data would be probably feasible).
As for Java, the best accepted solution has a total run time just below 2 s, which is the time limit for Java, so it’s definitely feasible as well.
Using my Core i7@2,2 GHz, I’m able to read your input and produce your output in about 0,5 s. SPOJ use Pentium G860@3 GHz. I don’t have this CPU, but its performance should be comparable in this case, so handling the I/O in under a second should be possible.
because we will enumerate the lower bound of the “extreme matrix”, and then, for given (i, j) and up[i][j], we would like to extend this vertical line to left and right as far as possible. Since the vertical height is fixed, “right[]” is similar to “left[]”. We can get “right[]” in a way similar to the way of getting “left[]”.