trjhtr

This is a follow-up question for HackerRank - Array Manipulation

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 $k$ and you have to add value
$k$ to all the elements ranging from index $a$ to $b$ (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

Final solution

I changed the way of storing the values, which now get indexed into a map. I think now it's efficient in time and space, my main questions left are about style (taking into account the impositions of the hacker rank input output).

#include <algorithm>
#include <iostream>
#include <map>

int main() 
 int n; int m;
 std::cin >> n >> m;
 using val_type = long long;
 std::map<int,val_type> map;
 while(m--)
 val_type start, end, val;
 std::cin >> start >> end >> val;
 map[start] += val;
 map[end+1] -= val;
 
 val_type max0;
 val_type partial_sum0;
 for (const auto& el : map) 
 partial_sum += el.second;
 if (partial_sum > max) 
 max = partial_sum;
 
 
 std::cout << max;
 return 0;

I don't like for example that I need to declare the variable partial_sum outside the for loop, being in the same scope as max. Any idea on how to write this partial sum to find the max cleaner?

Whitespace, let your code breathe

Your code has a few logical sections, you should use empty lines to break them appart visually. It makes your code easier to read.

Personal opinion: front-load your type aliases

General wisdom in C++ is to define things as close as possible to their first use, but that's generally meant for objects with lifetimes. I personally prefer to put any type alias at the start of its scope.

algorithm is unused, so it should not be included

Simple enough: do not #include stuff you don't need.

That's kind of it, really, good job!

Edit: to answer your question, you could finagle something with std::accumulate, or just create a scope for partial_sum, but it's not worth the trouble. What you have it fine.

1. Start with a comment telling what problem your code solves, possibly the algorithm you used, and a link to relevant references. You might want to quote part of them too!




2. You don't use anything from <algorithm>, so you should not include it. Well, if you follow the other tips, you will end up using it, but need <vector> and <utility> instead of <map>.




3. If you use constants, typedefs, preprocessor-symbols or the like to ease some customization or tuning, put them as early as possible, but after the includes.




4. Use the nomenclature of the reference, the subject-area if no reference, use descriptive names, or at least idiomatic ones.
   
   But refrain from inventing your own ad-hoc shorthand, that's cryptic instead of poignant.




5. There's nothing wrong with defining multiple variables at once, in principle.
   
   But they should be a single declaration, not multiple ones separated by semicolon.




6. Consider inserting a newline between sections to help readers easily find them.




7. Remember that input is often wrong. So check, or for such a short script, maybe enable exceptions on error.




8. Using a std::map works. But it's strictly speaking the wrong data-structure considering the access-pattern. Use a std::vector<std::pair<int, val_type>>, possibly with a call to .reserve(2 * m) to avoid re-allocation, and then do a std::sort().




9. Even the last line of output should be terminated with a new-line. Shells expect that, as do many other programs, and most users.




10. return 0; is implicit in main(), so no need to write it.