***Maximise Sum modulo

Maximise Sum

Problem Statement

You are given an array of size N and another integer M. Your target is to find the maximum value of sum of subarray modulo M.

Subarray is a continous subset of array elements.

Note that we need to find the maximum value of (Sum of Subarray)%M , where there are N∗(N+1)/2 possible subarrays.

Input Format
First line contains T , number of test cases to follow. Each test case consists of exactly 2 lines. First line of each test case contain 2 space separated integers N and M, size of the array and modulo value M.
Second line contains N space separated integers representing the elements of the array.

Output Format
For every test case output the maximum value asked above in a newline.

Constraints
2 ≤ N ≤ 105
1 ≤ M ≤ 1014
1 ≤ elements of the array ≤ 1018
2 ≤ Sum of N over all test cases ≤ 500000

Sample Input

1
5 7
3 3 9 9 5

Sample Output

6

Explanation

Max Possible Sum taking Modulo 7 is 6 , and we can get 6 by adding first and second element of the array

-------------------------------editorial------------------------------------

this problem can be done using binary search ..
we need to check all segment  with maximum mod ..

let j be the index than we need to check all i <j such that arr[i]--+-- arr[j] is maximum.

we create a prefix sum   from 0 to i , now lets say prefix sum %  k till i is x  than we search  till  i there is a  segment 0 to  s (s<i) such that its pfs sum <= x+1(lower bound of x+1).
if yes than  than answer will be max(maxi, pfi-(*it)+k)  {iterator found in lower bound}
bascically we are removing segment 0 to s and considering segmrnt s+1 to i

--------------------------------------------------authors editorial----------------------------------------------------

 Editorial by Devendra Agarwal

Let us denote Sum[i][j] = ( Prefix_Sum[i] - Prefix_Sum[j-1] )%M.

Here Sum[i][j] denotes the sum of all the elements from j to i.

Prefix_Sum[i] denotes the sum of all the elements from 1 to i.

Now, the problem is find the maximum value of Sum[i][j] for all i>=j.

Idea to solve this problem is quite similar to solving maximum sum subarray.

For a particular index i, we want to find the maximum for Sum[i][j] for some j.

Let pre[i] = Prefix_Sum[i] % M

Now , we want to find the value of pre[j] such that j

Note : Sum[i][j] = ( pre[i] - pre[j] )%M

pre[i] is constant for a given i.

So , only 2 cases are formed.

Case 1: pre[j] <= pre[i]

Find a pre[j] , such that , pre[j] is the smallest ( which is 0 , when you do not took any element )

Reason: If pre[i] > pre[j] then the difference is positive and is less than M. So , we need to find pre[j] which is the smallest and the smallest value is 0 (when you do not take any element).

Remember our target is to maximise ( pre[i] - pre[j] )%M at position i

Case 2: pre[j] > pre[i]

Now the minimum value for pre[i] - pre[j] is -(M-1) and the maximum value is -1.

Reason : pre[i]<pre[j] and M>pre[i],pre[j]>=0

Find pre[j] , which is just greater than pre[i].

Reason : The modulo answer will be M + pre[i] - pre[j] , M and pre[i] is constant , so we just need to find the minimum value of pre[j] which i s just greater than pre[i] in order to maximise the answer

Note : For finding the j in the second case , we will need balanced binary search tree.

We will take the maximum of both the cases and thus find the maximum of the (pre[i] - pre[j] )%M , for all j<=i in O(log(N)) time

Hack

The correct syntax for using lower_bound in C++ is set_object.lower_bound(value) , if you have used lower_bound(set_object.begin(),set_object.end(),value) , then you would have ended up in Time limit exceeded. 

-------------------------------------code----------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

typedef long int li;

#define test()    int test_case;cin>>test_case;while(test_case--)

#define fr(i,n) for(int i=0;i<n;i++)

#define frr(i,a,n) for(int p=i;p<n;p++)

#define sll(a) scanf("%lld",&a)

#define sl(a) scanf("%ld",&a)

#define si(a) scanf("%i",&a)

#define sd(a)  scanf("%ld",&a)

#define sf(a) scanf("%f",&a)

#define rn(a) return a

#define pai pair<int,int>

#define pal pair<li,li>

#define pall pair<lli,lli>

#define ff first

#define ss second

#define mod  1000000007

#define mp make_pair

#define pb push_back

#define pll(a) printf("%lld\n",a);

#define pl(a) printf("%lld\n",a);

#define pi(a) printf("%d\n",a);

#define pd(a) printf("%lf\n",a);

#define pf(a) printf("%f\n",a);

lli arr[10000000];

int main()

 {

  test()

  {

  lli n,k;

 

  sll(n);

  sll(k);

  set<lli> s;

  lli pre_sum=0;

     s.insert(0);

  lli maxi=-1;

  fr(i,n)

  {

 

  lli a;

  sll(a);

   

   

  pre_sum=(pre_sum+a)%k;

 

  maxi=max(maxi,pre_sum);

  set<lli> :: iterator it;

  it= s.lower_bound(pre_sum+1);

  if(it!=s.end())

   {

    maxi=max(maxi,pre_sum-*it+k);

}

  s.insert(pre_sum);

  }

   cout<<maxi<<endl;

 }

 rn(0);

 }