4177 - livada2

Sursa: 4177 - livada2

Fiind un băiat aventurier, călărețul Jonathan obișnuia să umble prin pădurile magice ale împărăției tatălui său. În interiorul meleagurilor lui, împăratul avea o livadă specială, în cadrul căreia se aflau n meri magici, numerotați de la 1 la n, fiecare măr i conținând o cantitate cunoscută m[i] de fructe. Fiind speciali, cantitatea de fructe din acești meri putea fi modificată. Ca în orice poveste, împăratul avea un dușman, pe vrăjitorul Afida, care dorea să-i atace livada. Cunoscând acest fapt, Jonathan, fiul împăratului, dorește să protejeze livada tatălui său. Cei doi se confruntă în livadă, fiecare făcând modificări asupra merilor. Există în total q modificări, fiind de două tipuri:

1 x y p: cantitatea de fructe din merii cu indici cuprinși între x și y crește cu p, fiind o modificare făcută de Jonathan

2 x y p: cantitatea de fructe din merii cu indici cuprinși între x și y scade cu p, fiind o modificare făcută de vrăjitorul Afida

Mai mult: În cadrul livezii împăratului, există câțiva meri extra magici care influențează modificările pe care le fac cei doi. Dacă în cadrul unei modificări a lui Jonathan, după y există un măr extra magic t, astfel încât între y și t nu există alt măr extra magic, interogarea cuprinsă între x și y se va transforma în interogare între x și t. Dacă în cadrul unei modificări a lui Afida, înaintea lui x există un măr extra magic t, astfel încât între t și x nu există alt măr extra magic, interogarea cuprinsă între x și y se va transforma în interogare între t și y.

Cerinţa

Să se afișeze cantitatea de fructe din fiecare măr după cele q modificări.

Date de intrare

Pe prima linie a fișierului livada2.in se găsește numărul n. Pe următoarea linie se găsesc n numere întregi, separate printr-un spațiu, al i-lea număr reprezentând cantitatea de fructe din mărul corespunzător. Pe următoarea linie se găsesc n numere, 0 sau 1, separate printr-un spațiu, valorile 1 indicând faptul că mărul de pe poziția i este extra special. Pe a 4-a linie se află numărul q de modificări. Următoarele q linii vor conține interogările, fiind de forma: c x y p. Dacă c=1, modificarea este făcută de Jonathan. Dacă c=2, modificarea este făcută de vrăjitorul Afida.

Date de ieșire

n fișierul livada2.out vor fi afișate n numere întregi separate prin câte un spațiu, reprezentând valorile din m, adică cantitatea de fructe a fiecărui măr.

Restricţii şi precizări

1 ≤ n ≤ 100.000
1 ≤ q ≤ 250.000
1 ≤ m[i] ≤ 1000, pentru 1 ≤ i ≤ n
Pentru 40 de puncte, q ≤ 1000 și n ≤ 1000
Pentru alte 20 de puncte, nu vor exista meri extra speciali

Exemplu

Intrare: 10; 17 18 2 21 14 6 13 14 8 10; 1 1 0 0 0 0 1 0 0 0; 7; 2 4 7 3; 1 8 9 16; 2 8 8 25; 2 4 4 8; 1 2 8 1; 2 8 9 21; 1 5 6 19
Ieșire: 17 8 -8 11 31 23 -16 -15 3 10

Rezolvare

Rezolvare ver. 1

4177 - livada2

def read_input():

   n = int(input())
   m = list(map(int, input().split()))
   is_extra = list(map(int, input().split()))
   q = int(input())
   queries = []
   for i in range(q):
       query = list(map(int, input().split()))
       queries.append(query)
   return n, m, is_extra, q, queries

def apply_query(n, m, is_extra, query):

   c, x, y, p = query
   x -= 1  # convertim la 0-indexing
   y -= 1
   t1, t2 = None, None
   for i in range(x, y+1):
       if is_extra[i]:
           if i < y and not t1:
               t1 = i
           if i > x and not t2:
               t2 = i
   if c == 1:  # modificarea lui Jonathan
       for i in range(x, y+1):
           if t1 and i > t1:
               break
           m[i] += p
   else:  # modificarea lui Afida
       for i in range(y, x-1, -1):
           if t2 and i < t2:
               break
           m[i] -= p

def validate(n, m):

   for i in range(n):
       assert m[i] >= 0

if __name__ == '__main__':

   n, m, is_extra, q, queries = read_input()
   for query in queries:
       apply_query(n, m, is_extra, query)
   validate(n, m)
   print(*m)

</syntaxhighlight>

Explicatie Rezolvare

Pentru a rezolva această problemă, vom crea o listă cu cantitatea de fructe din fiecare măr și o altă listă care va indica dacă un măr este extra magic sau nu. Vom itera prin fiecare modificare și vom actualiza cantitatea de fructe din mările afectate de aceasta. În timpul actualizării, vom verifica dacă modificarea este înainte sau după un măr extra magic și vom actualiza intervalul corespunzător. La final, vom afișa lista actualizată cu cantitatea de fructe. Funcția read_input() citește datele de intrare și le returnează sub formă de tuple. Funcția apply_query() primește o modificare și actualizează cantitatea de fructe din merii afectați de aceasta. Funcția validate() verifică că toate cantitățile de fructe sunt pozitive. În funcția main, citim datele de intrare, aplicăm modificările și validăm soluția.