HackerRank - Array Manipulation This is my implementation for this hacker rank problem. (And a follow-up.)

Problem


  You are given a list(1-indexed) of size n, initialized with zeroes.
  You have to perform m operations on the list and output the maximum of
  final values of all the  elements in the list. For every operation,
  you are given three integers a, b and  and you have to add value k to
  all the elements ranging from index  to (both inclusive).


Example input

5 3
1 2 100
2 5 100
3 4 100


Expected output

200


Explanation

After first update list will be: 

100 100 0 0 0


After second update list will be: 

100 200 100 100 100


After third update list will be: 

100 200 200 200 100


So the required answer will be: 200

First solution

My first attempt I think is quite readable (ignoring the way input and output is handle in hacker rank) 

#include &lt;bits/stdc++.h&gt;
#include &lt;algorithm&gt;

using namespace std;

int main() {
    int n, m;
    cin &gt;&gt; n &gt;&gt; m;
    vector&lt;long long&gt; v(n);
    for(int a0 = 0; a0 &lt; m; a0++){
        int start, end, val;
        cin &gt;&gt; start &gt;&gt; end &gt;&gt; val;
        auto it_start = v.begin()+(start-1);
        auto it_end = v.begin()+(end);
        transform(it_start, it_end , it_start, [k](long long &amp;x){return x+=k;});
    }
    cout &lt;&lt; *max_element(v.begin(),v.end());
    return 0;
}


Final solution

But this approach, although readable, is too slow for what it is actually being ask, which is the maximum value that it would be achieved. So I wrote this, which passed the tests, but which is more difficult to understand in my opinion.

#include &lt;algorithm&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;

int main() {
    int n; int m;
    std::cin &gt;&gt; n &gt;&gt; m;
    using val_type = long long;
    std::vector&lt;val_type&gt; v(n);
    while(m--){
        val_type start, end, val;
        std::cin &gt;&gt; start &gt;&gt; end &gt;&gt; val;
        auto it_start = v.begin()+(start-1);
        auto it_end   = v.begin()+ end;
        *it_start     += val;
        *it_end       -= val;
    }
    val_type max{0};
    auto accumulate_max_val = [x=val_type(0),&amp;max](val_type y) mutable{x+=y; if (x&gt;max) max=x;};
    std::for_each(v.begin(),v.end(),accumulate_max_val);
    std::cout &lt;&lt; max;
    return 0;
}


What would you do to improve it? Am I using lambdas and the for_each appropriately, or is there a clearer way to express what I want to do?
Kudos for figuring out the correct algorithm.

However you can streamline it by not using a v vector:

You correctly treated an operation a, b, k as a pair of operations: add k from a to the end, and subtract k from b+1 to the end. Now, instead of storing them in v, collect decoupled operations in a vector of their own. Sort it by index. std::partial_sum it, and find the maximum in the resulting array.

This will drive the space complexity down from \$O(n)\$ to \$O(m)\$, and change the time complexity from \$O(n+m)\$ to \$O(m\log m)\$. According to constraints, the time complexity seems to be better. One should also keep in mind that accesses to v could be all over the place with no particular order, and a well crafted sequence of operations may incur too many cache misses. I didn't profile though.
It is possible that spelling the loop out (rather than using for_each and lambda) would improve readability.
The algorithm would fail if k was allowed to be negative. Even it is not the case, it still is a good habit to initialize max and x to v[0], and start the loop at v.begin() + 1.