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 <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<long long> v(n);
for(int a0 = 0; a0 < m; a0++){
int start, end, val;
cin >> start >> end >> val;
auto it_start = v.begin()+(start-1);
auto it_end = v.begin()+(end);
transform(it_start, it_end , it_start, [k](long long &x){return x+=k;});
}
cout << *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 <algorithm>
#include <vector>
#include <iostream>
int main() {
int n; int m;
std::cin >> n >> m;
using val_type = long long;
std::vector<val_type> v(n);
while(m--){
val_type start, end, val;
std::cin >> start >> end >> 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),&max](val_type y) mutable{x+=y; if (x>max) max=x;};
std::for_each(v.begin(),v.end(),accumulate_max_val);
std::cout << 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?