“Algorithmic Crush” problem hitting timeout errors

A few general coding style suggestions:

• Rather than assigning M and N on separate lines, you can use tuple unpacking:

  N, M = tempArray
  

• I'd use different variable names for the first input line, and all subsequent lines. For example:

  init_line = [int(n) for n in input().split()]  # split() defaults to whitespace
  size_of_list, number_of_operations = init_line
  
  for i in range(number_of_operations):
      this_line = [int(n) for n in input().split()]
      # Do some stuff
  

  I’ve also changed the other variable names: M and N have been replaced by more descriptive names, and the Python convention is to use snake_case, not dromedaryCase.

  Or even better, you could just drop those variables entirely:

  size_of_list, number_of_operations = [int(n) for n in input().split()]
  
  for i in range(number_of_operations):
      a, b, k = [int(n) for n in input().split(" ")]
  

  Note the tuple unpacking for a, b and k: this makes it easier to follow the logic if we have these named variables.

• In the look over M/number_of_operations, since the value of i is unused, a common convention is to use an underscore instead:

  for _ in range(number_of_operations):
  

The time complexity is actually \$O(MN)\$, because there’s an outer loop of length M, and inner loop of length N, and a single addition for every step.

I can’t see a good way to improve the time complexity. Some people have suggested other data structures in the comments, but I don’t know enough CS to suggest one myself.

Constraints

\$3 ≤ N ≤ 10^7\$
\$1 ≤ M ≤ 2 \cdot 10^5\$
\$1 ≤ a ≤ b ≤ N\$
\$0 ≤ k ≤ 10^9\$

You should verify that every value you read from the user is a valid value in your program.

As far as complexity goes, a suffix tree with a complexity of \$O(N\log{}N)\$ compared to your current \$O(MN)\$ solution that adds difference to every value in the range \$[A,B]\$. With \$N \sim 10^7\$, an \$O(N\log{}N)\$ solution may still be too slow.

For this problem, I would employ a max prefix sum scan on a difference array. To generate a set of range differences, we adjust \$arr_{a} \mathrel{{+}{=}} k\$ and \$arr_{b+1} \mathrel{{-}{=}} k\$. Going back to your sample data, your difference array would look like this:

         #   1.......................N...N+1
5 3      #   0     0     0     0     0     0
1 2 100  # 100     0  -100     0     0     0       
2 5 100  # 100   100  -100     0     0  -100
3 4 100  # 100   100     0     0  -100  -100

To calculate the max prefix sum, accumulate the difference array to \$N\$ while taking the maximum accumulated prefix. (*) denotes new max found.

DiffArray  100  100    0    0  -100  -100
PrefixSum  100*
Max = 100

DiffArray  100  100    0    0  -100  -100
PrefixSum       200*
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum            200
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum                 200
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum                       100
Max = 200

Building a difference array in \$O(M)\$ and finding the max prefix sum in \$O(N)\$ results in a \$O(M+N)\$ linear algorithm.