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

general
, , ,
1

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.

[CHEFEXQ]
1

My submission getting only 50

Edit:

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

2 
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.

3

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
4

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: