1512 - Mars

Cerinţa

Se consideră un tablou unidimensional cu n elemente numere întregi, numerotate de la 1 la n, inițial toate nule. Asupra tabloului se fac m operații s d X cu semnificația: toate elementele cu indici cuprinși între s și d își măresc valoarea cu X.

Să se afișeze tabloul după realizarea celor m operații.

Date de intrare

Programul citește de la tastatură numerele n m, iar apoi m triplete s d X, cu semnificația din enunț.

Date de ieșire

Programul va afișa pe ecran cele n elemente ale tabloului, separate prin exact un spațiu.

Restricţii şi precizări

1 ≤ n ≤ 200.000
1 ≤ m ≤ 200.000
1 ≤ s ≤ d ≤ n
-1000 ≤ X ≤ 1000

Exemplu

Intrare: 10 6; 8 10 2; 3 10 -3; 5 9 7; 5 5 5; 6 7 2; 1 1 -1
Ieșire: -1 0 -3 -3 9 6 6 6 6 -1

Rezolvare

Rezolvare ver. 1

1512 - Mars

def read_input():

   n, m = map(int, input().split())
   return n, m, [0] * n

def update_array(arr, s, d, X):

   for i in range(s-1, d):
       arr[i] += X

def solve(n, m, arr):

   for _ in range(m):
       s, d, X = map(int, input().split())
       update_array(arr, s, d, X)
   return arr

def validate(n, m, arr):

   assert len(arr) == n

if __name__ == '__main__':

   n, m, arr = read_input()
   arr = solve(n, m, arr)
   validate(n, m, arr)
   print(*arr)

</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input() primește datele de intrare de la utilizator și returnează n, m și tabloul inițial. Funcția update_array() primește un tablou arr, o pereche de indici s și d și o valoare X, și actualizează toate elementele din arr cu indici cuprinși între s și d astfel încât să fie adăugate la ele valoarea X. Funcția solve() primește n, m și tabloul inițial, iterează prin cele m operații și actualizează tabloul conform operațiilor. Funcția validate() verifică dacă tabloul rezultat are lungimea corectă. În if __name__ == '__main__', apelăm funcțiile în ordine pentru a rezolva problema și afișăm tabloul rezultat.