C++ | Prefix sum + Binary Search
Code

# Code
```cpp []
class Solution {
public:
    #define ll long long
    int LB(vector<vector<int>>& coins, int x)
    {
        int n=coins.size();
        if(x<coins[0][0])
            return -1;
        if(x>coins[n-1][1])
            return n;
        int l=0,h=n-1,res;
        while(l<=h)
        {
            int mid=(l+h)/2;
            if(coins[mid][0]>x)
            {
                res=mid;
                h=mid-1;
            }
            else if(coins[mid][1]<x)
               l=mid+1;
            else
                return mid;   
        }        
        return res;
    }
    int UB(vector<vector<int>>& coins, int x)
    {
        int n=coins.size();
        if(x<coins[0][0])
            return -1;
        if(x>coins[n-1][1])
            return n;
        int l=0,h=n-1,res;
        while(l<=h)
        {
            int mid=(l+h)/2;
            if(coins[mid][1]<x)
            {
                res=mid;
                l=mid+1;
            }
            else if(coins[mid][0]>x)
               h=mid-1;
            else
                return mid;   
        }        
        return res;
    }
    long long maximumCoins(vector<vector<int>>& coins, int k) 
    {
        sort(coins.begin(), coins.end());
        ll res=0,n=coins.size();
        vector<ll>prefix(n+1,0);
        for(int i=0;i<n;i++)
        {
            prefix[i+1]=prefix[i]+(ll)coins[i][2]*(coins[i][1]-coins[i][0]+1LL);
        }
        for(int i=0;i<n;i++)
        {
            // Case:1
            int start=coins[i][0],end=start+k-1;
            int j=LB(coins,end);
            ll curr=prefix[j]-prefix[i];
            if(j<n)
               curr+=1LL*max(0LL,(end-coins[j][0]+1LL))*coins[j][2];
            res=max(res,curr);   

            //Case:2
            start=coins[i][1],end=start-k+1;
            j=UB(coins,end);
            curr=prefix[i+1]-prefix[j+1];
            if(j>=0)
                curr+=1LL*max((coins[j][1]-end+1LL),0LL)*coins[j][2]; 
            res=max(res,curr);      
        }
        return res;
    }
};
```
['C++']