By WrongAnswerOnTestcase1, history, 4 days ago,

I have implemented as per the algorithm suggested in the EDU section (here), however it gets MLE for some reason. The memory complexity should be O(m log m) which shouldn't be too much.

Can anyone tell me how to optimize this code (for Step 3 Problem C — Dynamic Connectivity Offline) for memory. I believe my code is logically correct, however it get MLE on (hidden) testcase 2. I have tried all the optimizations I could think of.

Also I think that the pseudocode in the EDU section (here) is not correct. In the base case, we should apply the unions applicable over that leaf, since the query segment could have been split in such a way that it covers only the leaf. Please correct me if I am wrong.

Here is my code.

• 0

 » 4 days ago, # |   0 anyone?
 » 4 days ago, # | ← Rev. 2 →   0 Try to came up with $stack$ approach of persistent DSU.$map >$ is also bad, it's possible to do it with $map$
•  » » 4 days ago, # ^ | ← Rev. 4 →   0 I did both the optimizations, still the same MLE.updated code
•  » » » 4 days ago, # ^ |   0 ML in this problem is really tough. My submission uses ~183/256 mb.Try another two optimizations: firstmake your on stack with array(int[]) and pointer. seconddon't store ask_ queries, just make bool need[] where need[t] = 1, if and only if you have ask_ query in position t.You can check my OK submission to understand details.
•  » » » » 4 days ago, # ^ |   0 Something weird is happening. I thought it was MLE, but actually it shows "Runtime Error on test 2" with memory used = 262100 KB, so I thought it was MLE. I changed my approach to segment tree like method where I precompute all the segments where add/remove queries happen. Weird enough, this submission still shows "Runtime Error on test 2" with memory used = 28200 KB. I have no idea how runtime error is happening.segment tree like code
•  » » » » » 4 days ago, # ^ |   0 Btw, you may still have MLE, but your code falls with seg fault earlier ,than you used all the memory.So, I guess, you code doesn't work logically correct, as you wish)I don't see any serious errors in your code, try stress-testing, maybe you can catch seg fault. You may also you -fsanitize flags to help you.
•  » » » » » » 4 days ago, # ^ |   0 Thanks a lot for the help. It ended up being a minor mistake, i was not considering edge (u,v) and (v,u) to be same. Anyway, I ended up getting 28300 KB memory.submission