Hotel

hotel

==Include(page="template/taskheader" task_id="hotel")==

== include(page="template/taskheader" task_id="hotel") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| hotel.in | hotel.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="hotel") ==

==Include(page="template/raw")==
 
Hotel
 
 
 
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:
 
S 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.
 
S 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.
 
S 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:
 
S 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
 
S 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
 
S 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
 
S 3 <= N <= 100.000
 
S 3 <= P <= 200.000
 
S In orice camera poate fi cazat la un moment dat un singur turist.
 
h2. Exemplu
 
hotel.in hotel.out
 
12 10 12
 
3 4
 
1 2 3 4
 
1 9 4 6
 
3 10
 
2 2 1
 
3
 
2 9 2
 
3
 
2 3 2
 
3
==Include(page="template/taskfooter" task_id="hotel")==