== include(page="template/taskheader" task_id="hotel") ==
==Include(page="template/taskheader" task_id="hotel")==
Poveste ...
Hotelul "Informatica" este unul dintre cele mai luxoase hoteluri din Galaciuc. De-a lungul anului multe grupuri de turisti sosesc la acest hotel sau il parasesc la sfarsitul sejurului, asa ca situatia exacta a camerelor libere si ocupate este destul de greu de aflat, mai ales ca hotelul are un numar mare de camere. Dar anul acesta proprietarul hotelului s-a decis ca are nevoie de o schimbare. De aceea v-a angajat pe dumneavoastra pentru a scrie un program eficient, care sa raspunda necesitatilor sale.
h2. Cerinta
...
Scrieti un program care sa trateze in mod eficient urmatoarele $3$ tipuri de instructiuni:
* tipul $1$: sosirea unui grup nou de turisti
Un grup de turisti avand $M$ membri vrea sa ocupe $M$ camere libere numerotate consecutiv. Programului $i$ se va furniza numarul $i$ al camerei de inceput al secventei de camere ocupate de grup si numarul $M$ de membri ai grupului. Se garanteaza ca oricare din camerele $i,i+1,.., i+M-1$ este libera la momentul respectiv.
* tipul $2$: plecarea unui grup de turisti
Atunci cand pleaca, turistii pleaca in grupuri (nu neaparat cele cu care au venit). Un grup care pleaca si care are $M$ membri paraseste $M$ camere (anterior ocupate) numerotate consecutiv. Programului $i$ se va furniza numarul $i$ al camerei de inceput al secventei de camere eliberate, precum si numarul $M$ de membri ai grupului. Se garanteaza ca toate camerele cu numerele de ordine $i,i+1,..,i+M-1$ sunt deja ocupate de turisti.
h2. Restrictii
* tipul $3$: intrebarea proprietarului
...
Proprietarul hotelului poate sa intrebe, din cand in cand, care este lungimea maxima a unei secvente de camere libere numerotate consecutiv. El are nevoie de acest numar pentru a putea sti care este numarul maxim posibil de membri ai unui grup care ar putea fi cazati la hotelul "Informatica".
h2. Date de intrare
...
Pe prima linie a fisierului $hotel.in$ se vor afla numerele $N$ si $P$, reprezentand numarul de camere ale hotelului (numerotate de la $1$ la {$N$}), respectiv numarul de instructiuni care urmeaza. Pe fiecare din urmatoarele $P$ linii se va afla un numar $c$, reprezentand tipul instructiunii ce va fi descrisa pe linia respectiva:
* daca $c$ are valoarea $1$, atunci el va fi urmat (pe aceeasi linie) de alte $2$ numere, $i$ si $M$, reprezentand numarul primei camere distribuite grupului abia sosit si numarul de membri ai grupului
* daca $c$ are valoarea $2$, atunci el va fi urmat (pe aceeasi linie) de alte $2$ numere, $i$ si $M$, reprezentand numarul primei camere care va fi eliberata de grupul care tocmai pleaca, precum si numarul de membri ai grupului care paraseste hotelul
* daca $c$ are valoarea $3$, el nu va fi urmat de nici un alt numar pe linia respectiva; programul va trebui, insa, sa afiseze in fisierul de iesire lungimea maxima a unei secvente de camere libere numerotate consecutiv.
h2. Date de iesire
...
In fisierul hotel.out veti afisa, pentru fiecare instructiune de tipul 3, pe cate o linie separata, lungimea maxima a unei secvente de camere libere numerotate consecutiv, luand in considerare instructiunile de tipul 1 si 2 aflate in fisierul de intrare inaintea instructiunii de tip 3 la care se raspunde. Inaintea primei instructiuni, toate camerele sunt libere.
h2. Restrictii si precizari
* $3 ≤ N ≤ 100.000$
* $3 ≤ P ≤ 200.000$
* In orice camera poate fi cazat la un moment dat un singur turist.
h2. Exemplu
| hotel.in | hotel.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. hotel.in |_. hotel.out |
| 12 10
3
1 2 3
1 9 4
3
2 2 1
3
2 9 2
3
2 3 2
3
| 12
4
4
6
10 |
== include(page="template/taskfooter" task_id="hotel") ==
==Include(page="template/taskfooter" task_id="hotel")==
