can someone help in optimizing my solution /give some tips to avoid such tle’s in future
it uses the same idea as the editorials but is getting tle even on the small subtask.
One thing I noticed is that you process the vector back from the front, but since we restore operations in reverse it should be from the back.
I don’t know if this causes TLE, though.
tried it in the other way also.sadly still tle even on subtask 1 @tmwilliamlin
No offence,but before asking debugging questions to community you should test it on random test cases and see why it’s getting tle.also you should try to change seg tree implementation,use from any good source, and then try to figure what is the root cause, seg tree or something other.
well the seg tree is fine with right complexity and implementation
its just that the solution of this problem is nlogn^2 which requires lot of constant optimizations to pass in the tight time limit. also I debugged for a lot of time and couldn’t find anything so posted it here and asked for help.you can see how many submissions I made for this problem
if it doesn’t even pass subtask 1 then it’s not a constant optimization issue
in my opinion also its a problem of constant optimization. because i have used your same approach then also it is getting TLE.
MY Submission link : https://www.codechef.com/viewsolution/30015560
please look into this matter sir.
This is obviously not a constant optimization issue. This algorithm is nowhere near O(n^2), so passing n<=5000 shouldn’t be a problem. You probably have a bug in your implementation.
This is not FFT, this is just segtree constant. 3e6 is very fast
But sir my implementation is almost similar to you. just only passing the parameter in function is changed. pls check it once again sir.
Yea 3e6 operations is 0.01s, nowhere near TLE lol.
Sir, please help me also…
You have the same problem.
tmwilliamlin is correct you are also building segment tree in wrong way.