1512 - Mars

Sursa: 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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou n elemente ale tabloului, separate prin exact un spațiu, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

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

Exemplu 1

Intrare

10 6

8 10 2

3 10 -3

5 9 7

5 5 5

6 7 2

1 1 -1

Ieșire

Datele sunt introduse correct

-1 0 -3 -3 9 6 6 6 6 -1

Exemplu 2

Intrare

5 5 1 1

1 5 1

1 5 2

1 5 3

1 5 4

1 5 5

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 1512 - Mars


def solve(n, m, operations):
    arr = [0] * n  # initializeaza lista cu n elemente nule
    
    for i in range(m):
        s, d, x = operations[i]
        arr[s-1:d] = [el + x for el in arr[s-1:d]]
    
    return arr

def main():
    n, m = map(int, input().split())

    # Validare intrare
    if not 1 <= n <= 200000 or not 1 <= m <= 200000:
        print("Datele nu corespund restricțiilor impuse.")
        return

    operations = []
    for i in range(m):
        s, d, x = map(int, input().split())
        if not 1 <= s <= d <= n or not -1000 <= x <= 1000:
            print("Datele nu corespund restricțiilor impuse.")
            return
        operations.append((s, d, x))

    # Afiseaza rezultatul
    print("Datele sunt introduse corect.")
    result = solve(n, m, operations)
    print(*result)  # afiseaza elementele listei separate prin spatii

if __name__ == '__main__':
    main()

Explicatie Rezolvare

Funcția solve primește dimensiunea listei n, numărul de operații m și lista de operații operations. Inițializează lista cu n elemente nule. Apoi, pentru fiecare operație, actualizează intervalul corespunzător din listă cu valoarea x. Dacă s=1 și d=n, putem utiliza notația slicing arr[s-1:d] pentru a accesa intervalul. De asemenea, putem utiliza o list comprehension pentru a aplica operația asupra fiecărui element din interval. Funcția main citește valorile n și m de la tastatură. Apoi citește cele m operații și validează fiecare operație în parte. Dacă valorile citite nu respectă restricțiile impuse, se afișează un mesaj corespunzător și se oprește execuția programului. Dacă toate valorile sunt valide, se afișează un mesaj de confirmare și se apelează funcția solve pentru a calcula tabloul final. Rezultatul este afișat pe un singur rând, cu elementele separate prin spații. Funcția main este apelată doar dacă programul este rulat direct, nu importat ca modul.