Look, what’s the max amount of sum(l,r)%p? It’s p-1! So we have that sum on prefix (0,r)=x, than sum on prefix(0,r) - sum on prefix(0,l-1)=p-1 => - sum on prefix(0,l-1)=p-1 - sum on prefix(0,r) => sum on prefix(0,l-1)=1 + sum on prefix(0,r) - p =>sum on prefix(0,l-1)=1 + sum on prefix(0,r)
1
3 1000000000
1000000000 1000000000 1000000000
Your solution output 0 5, but must be 0 6. Think about it
s += a[x] % p, this line, if p = 1000000000, and array = {999999999, 999999999, …, …}, then value s will overflow
1 Like
how should it be for the code to produce AC?
at first, use long long or be very neat with modulo p
Thank you.
@glebodin: It is \mathcal{O}(log N). Underlying structure in set is balanced binary search trees (BBSTs). In BBST, the following property is held for each node. For each node x, the value at its left child is \leq the value at x, and the value at the right child will be \geq value at x. So, you can find first element greater than or equal to some value by making a comparison at each node starting from root and deciding which child to go, to the left or to the right. The max number of comparisons will equal to the height of the tree, which is \mathcal{O}(log N) for BBST.
1 Like
1 3 1000000000 1000000000 1000000000 1000000000 Your solution output 0 5, but must be 0 6. Think about it(overflows sum[n]>2^32)
s overflows in your code, s=s+arr[i+j];
Aren’t the problems for Lunchtime supposed to be new?
Read my solution, I think it’s better for novice!
Most of us have the question, why we try to take the value of y immediate larger of x and if no larger value than x is present in Z then take min value from Z (i.e. 0) for this { sum = (x + p - y) % p } equation to get the maxSum.
Okay, let’s take a look below:
sum = (x + p - y) % p (why % p? To avoid negative value, you can say it’s a rule)
Assume x = 3, p = 8
if we take y = 4, sum = (3 + 8 - 4) % 8 = 7
if we take y = 5, sum = (3 + 8 - 5) % 8 = 6
if we take y = 6, sum = (3 + 8 - 6) % 8 = 5
if we take y = 7, sum = (3 + 8 - 7) % 8 = 4
we can’t take y larger than p because our set Z only contains the values % p
Now, if the Z hasn’t larger value than x, then check from y = 0
if we take y = 0, sum = (3 + 8 - 0) % 8 = 3
if we take y = 1, sum = (3 + 8 - 1) % 8 = 2
… and so on.
So, we can say that if any larger value is present in set Z then take y as the immediate larger value of x, if not then take y = 0 (i.e. 0 to i segment).