***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);

 }

Kefa and Company

 Kefa and Company

Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

Input

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 105, ) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa's friends, the (i + 1)-th line contains the description of the i-th friend of type mi, si(0 ≤ mi, si ≤ 109) — the amount of money and the friendship factor, respectively.

Output

Print the maximum total friendship factir that can be reached.

Sample test(s)

input

4 5
75 5
0 100
150 20
75 1

output

100

input

5 100
0 7
11 32
99 10
46 8
87 54

output

111

Note

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

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

sort according to money and for ith persone find lower_bound of arr[i]+d...

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

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll dp[100010];
int main()
{
    ll n, d;
    cin>>n;
    ll ans=0;
    cin>>d;
    vector<pair<ll, ll> > v;
    ll a ,b;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end());
    dp[0]=v[0].second;
    for(int i=1;i<n;i++)
    {
         dp[i]=v[i].second+dp[i-1];
    }
    vector<ll> v1;
    for(int i=0;i<n;i++)
    {
          v1.push_back(v[i].first);
    }
    vector<ll> ::iterator it;
    for(int i=0;i<n;i++)
    {
         ll s=v[i].first+d-1;
    //   cout<<"search "<<s<<endl;
         ll temp;
         it=upper_bound(v1.begin()+i,v1.end(),s);
    //    cout<<"get "<<*it<<endl;  
            it--;
            int pos=it-v1.begin();
            if(i!=0)
            temp=dp[pos]-dp[i-1];
            else
            temp=dp[pos];
    //   cout<<temp<<endl;
         ans=max(temp,ans);
    }
    cout<<ans<<endl;
    return 0;
}