I was learning sqrt decomposition, to practise for the same i was solving http://www.spoj.com/problems/UNTITLE1/ problem on spoj, but i am continously getting SIGSEGV error for the same, i tried my level best to debug it but was unable to solve it,moreover there is no online reference for this particular problem,
i know the hopes of getting myself help is low but still if someone wanna help , here is my code http://ideone.com/jePYPu , i tried to make it as clean as possible.
It is not true that . Counter example: n = 3.
Compiling with
g++ -g -fsanitize=address -fsanitize=undefined
and executing with n = 3 input gives this message:Line 99 is
bsum[(int)i/rootn]+=arr[j];
. Asn = 3
,rootn = 1
andsz = bsum.size() = 2
, wheni
reachn - 1
,bsum[(int)i/rootn]
will be out of bounds, causing undefined behavior.Unfortunately even if you fix this bug you will still get TLE.
thanks for identifying that bug, i fixed that and for avoiding TLE i used D.P and constant optimization too, but still it gives a TLE, is there a way out ?
my new code : http://dpaste.com/3RS4GN0
You have to remember the largest Si in each block.
For a partial block update, you can just spent .
For a full block update, you have to answer y = maxi(Si + ix) over i for some x. See http://wcipeg.com/wiki/Convex_hull_trick#The_technique if you don't know how to do that.