C++ | Prefix Sum + Binary Search
IntuitionApproachComplexity

Time complexity:
O (n log n)


Space complexity:

Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
O (n log n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:

#define ll long long
#define is ==
#define isnt !=

    long long maximumCoins(vector<vector<int>>& num, int k) {

        sort (num.begin (), num.end ()) ;

        vector <vector <ll>> x ;

        for (int i = 0 ; i < num.size () ; i ++) {

            vector <ll> t ;

            t.push_back (num [i][0]) ;

            t.push_back (num [i][1]) ;
            
            t.push_back (num [i][2]) ;

            x.push_back (t) ;
            
        }

        ll n = x.size () ;

        for (int i = 0 ; i < n ; i ++) cout << x [i][0] << ' ' << x [i][1] << ' ' << x [i][2] << endl ;

        ll ans = 0 ;

        vector <ll> pref (n), l (n), r (n) ;

        pref [0] = (x [0][1] - x [0][0] + 1) * x [0][2] ;

        for (int i = 1 ; i < n ; i ++) pref [i] = pref [i - 1] + (x [i][1] - x [i][0] + 1) * x [i][2] ;

        for (int i = 0 ; i < n ; i ++) l [i] = x [i][0], r [i] = x [i][1] ;

        for (int i = 0 ; i < n ; i ++) {

            ll run = 0 ;
    
            ll c = r [i] - k + 1 ;

            if (c <= 0) continue ;

            ll lb = lower_bound (r.begin (), r.end (), c) - r.begin () ;

            run = (r [lb] - max (c, l [lb]) + 1) * x [lb][2] + pref [i] - pref [lb] ;

            ans = max (ans, run) ;
            
        }

        for (int i = 0 ; i < n ; i ++) {

            ll run = 0 ;

            ll c = l [i] + k - 1 ;

            ll lb = upper_bound (l.begin (), l.end (), c) - l.begin () ;

            lb -- ;

            run = (min (r [lb], c) - l [lb] + 1) * (x [lb][2]) + (lb ? pref [lb - 1] : 0) - (i ? pref [i - 1] : 0) ;

            ans = max (ans, run) ;
        }

        return ans ;
    }

};
```
['Binary Search', 'Prefix Sum', 'C++']