culori2

Culori2

== include(page="template/taskheader" task_id="culori2") ==

Poveste si cerinta...

Muncitorii de la cooperativa $Munca-n zadar$ au la dispozitie o teava cu lungimea de $N$ metri. Initial aceasta teava are culoarea $C$. Muncitorii pot taia o bucata de teava in doua bucati de lungimi intregi si revopsi cele doua bucati. Muncitorii pot sa se si razgandeasca si sa sudeze la loc doua bucati inapoi in bucata mare din care au fost despartite si sa o revopseasca cu culoarea pe care o avea inainte de taiere. Prin taiere sau sudare bucatile de tevi nu se muta din locul lor initial si deci o bucata de teava poate fi identificata prin pozitia ei. Pozitia unei bucati de teava este specificata prin distanta dintre inceputul tevii initiale si inceputul bucatii de teava exprimata in metri.
 
h2. Cerinta
 
Lucrati la aceasta cooperativa si trebuie sa scrieti un program care implementeaza urmatoarele comenzi:
 
* $SPLIT (P L CL CR)$: bucata de teava care incepe la pozitia $P$ va fi impartita in doua bucati mai mici, cea din stanga avand marimea $L$. Apoi bucata din stanga va fi colorata cu culoarea $CL$ si cea din dreapta cu culoarea $CR$. Se garanteaza ca $0$ < $L$ < lungimea bucatii de teava care trebuie impartita
* $UNDO (P)$: bucata care incepe la pozitia $P$ se va resuda cu bucata imediat din dreapta ei. Se garanteaza ca in momentul apelarii acestei comenzi bucata imediat din dreapta ei este cea obtinuta prin aceeasi operatie de taiere in urma careia a rezultat bucata de la pozitia $P$ (chiar daca se poate ca oricare dintre cele doua bucati sa fi fost taiate si resudate). Bucata rezultata se va recolora in culoarea pe care o avea inainte de taiere
* $GETCOLOR (P)$: se afiseaza culoarea bucatii care incepe la pozitia $P$
 
Pentru toate comenzile, va exista o bucata de teava care sa inceapa la pozitia $P$.

h2. Date de intrare

...

Fisierul $culori2.in$ contine pe prima linie numerele $N$, $C$ si $M$, separate printr-un spatiu. Fiecare dintre urmatoarele $M$ linii contine o comanda. Comenzile sunt codificate astfel:
 
* $SPLIT (P L CL CR)$ -> $2 P L CL CR$
* $UNDO (P)$ -> $1 P$
* $GETCOLOR (P)$ -> $0 P$

h2. Date de iesire

...

Fisierul $culori2.out$ va contine atatea linii cate comenzi $GETCOLOR$ sunt, reprezentand culorile respective, in ordinea comenzilor $GETCOLOR$ corespunzatoare.
 

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 524288 (2^19^)$
* $1 ≤ M ≤ 2 000 000$
* Toate culorile au valori cuprinse intre $0$ si $255$ (inclusiv)
* Pozitiile vor fi numere intregi intre $0$ la $N-1$ (inclusiv)

h2. Exemplu
table(example). |_. culori2.in |_. culori2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 11 3 13
  2 0 8 1 3
  1 0
  2 0 10 3 0
  0 0
  2 0 9 1 1
  2 0 8 2 3
  1 0
  2 0 5 2 3
  1 0
  2 0 5 3 2
  0 9
  1 0
  0 0
| 3
  1
  1

|

h3. Explicatie

== include(page="template/taskfooter" task_id="culori2") ==

...
== include(page="template/taskfooter" task_id="culori2") ==

1853