CHEFEXQ-Can't find out what is giving me SIGSEGV and WA on last subtask.

Please help me figure out what is wrong in my implementation of sqrt decomposition for CHEFEXQ.

I tried hard, but couldn’t find.

I am a beginner in implementing sqrt decomposition.


My submission getting only 50


I changed ‘int mp[SQ][1222222]’ to ‘unordered_map’ , and now I am getting SIGFPE.

Please help!

Link to your solution with little bit explanation of it will also be helpful.

Changed solution

int mp[SQ][1222222];

SQ being around 300 makes this take 4*{10}^{8} alone itself. I think thats quite past the memory limit, hence SIGSEV.

Redefine SQ to const int SQ=(int)sqrt(N)+10;

You are going out of bounds in unordered map. After this you’d get TLE, so make unordered map faster by reserve trick and see.

1 Like

Arrays were going out of bounds due to SQ.
I increased it as you said.
And for TLE, int mp[SQ][1050000] memory worked instead of unordered_map.
I didn’t know this much memory will be allowed.
Thanks for your efforts!! :slight_smile: