arr[-1]=0; Is it legally? 
I thought that too. But itās working everywhere (GCC, Codechef Ide, Ideone), doesnāt it? But during submission on Codechef, it throws WA. Iām looking for alternative of that but as of now, please let me know if Iāve done something wrong there.
1
5 5
5 5 5 5 5
Your solution output 20, but answer is 15, your process empty segments
1 Like
just 5 5 0 0 0 0 0? what about p?
Why N log^2 N? For me, itās N log N
Got it. 1 5 5 5 5 5 5 5 it is.
bin.search in set is log^2, is not it?
No, log(N)
1 Like
Ok, thanks
Ok, but i think your solution is too hard for novice, so letās do this 1) letās go from i=0 to n and add a[i] to sum 2) then we need the first number >=(sum+1+p)%p because (sum-(sum+1)+p)%p=p-1; so letās make bin.search to the set for number>=(sum+1+p)%p so itās work Nlog(N) (link: Y8l5mm - Online C++0x Compiler & Debugging Tool - Ideone.com )
If you donāt understand, say me!
I donāt know anything about sets/maps/pairs. I canāt quite understand your code.
" we need the first number >=(sum+1+p)%p because (sum-(sum+1)+p)%p=p-1"
Can you please elaborate what you mean?
I really appreciate the help, buddy
ok, letās count the sum on prefixs! Then the sum of every subarray is the sum on prefix(0,r)-prefix(0,l-1)!
Thatās about subtask 2, I understood it completely.
Then letās go from prefix(0,0) to(0,n-1)! Letās firstly find the most optimal prefix,that give the closest to p number and then add new prefix to our list of prefixes !
ok, what is the most optimal prefix? Itās the prefix, which gives sum on prefix(0,x)+1 or more! ( because sum on prefix(0,x)-(sum on prefix(0,x)+1) gives -1, which is equal to p-1)
then how to save all prefixes
- vector, but itās n^2
- we can save the amount of every prefix in array,but itās give p memory and pn time;
- then you can do set!
what is your language(c++,java, pascal)?
itās the habit, itās not Obligated
and why we are adding 1?
what does this line means (sum-(sum+1)+p)%p=p-1??
tell me the meaning /significance of this line???