We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • vadim_tarasov
     + 0 comments

    My solution, O(M*log(M)):

    #include <cstdint>
#include <map>
#include <iostream>

int main()
{
  std::uint64_t N;
  std::uint64_t M;
  std::cin >> N;
  std::cin >> M;
  std::int64_t max = 0;
  
  std::uint64_t A;
  std::uint64_t B;
  std::uint64_t k;
    
  std::map<std::uint64_t, std::int64_t> points;

  for (std::uint64_t i = 0; i < M; ++i) {
    std::cin >> A;
    std::cin >> B;
    std::cin >> k;
    
    points[A] += k;
    points[B + 1] -= k;
  }

  std::int64_t value = 0;
  for (auto it = points.begin(); it != points.end(); ++it) {
    value += it->second;
    if (value > max) {
      max = value;
    }
  }
  std::cout << max;
  return 0;
}

    It is not necessery to store full array. It is sufficient to store only begins and ends of all intervals (A and B). For example, if you have 10^7 elements and one operation, you need only 2 points, not 10^7. But in some languages (for example pure C) you will need to implement someone ordered container with fast insert operation, for example ordered List.