Compania feroviara isi propune
sa modernizeze sistemul actual de organizare a trenurilor. O parte importanta
este cea de gestiune a componentei trenurilor si clasificarea in functie de
calitate a vagoanelor.
CF a asociat fiecarui vagon
un numar calitativ si inregistreaza de-a lungul timpului toate operatiile care
se fac pentru formarea trenurilor, vrand ca avand aceste informatii sa poata
realiza o repartitie inteligenta a claselor de pasageri intr-un segment de tren
in functie de nivelul minim de calitate pe acel segment.
Problema:
Se porneste initial de
la un vector de N numere naturale
reprezentand nivelul de calitate ale tuturor vagoanelor in ordine, ele fiind
plasate initial in lant in depoul companiei. Acest vector are numarul de identificare
0.
Trebuiesc simulate o serie
de M operatii, codificate astfel
in fisierul de intrare:
S
ID POS IDDR
Se imparte vectorul
cu identificatorul ID in
doi vectori formati din elementele de pe pozitiile:
1,2,..POS
si respectiv POS+1,POS+2,..LungimeVectorInitial,
Prima parte isi va pastra
identificatorul, iar cel de-al doilea vector va primi identificatorul IDDR.
J
IDST IDDR
Se concateneaza vectorii
identificati IDST si IDDR
in aceasta ordine, vectorul obtinut va avea identificatorul IDST
si vectorul identificat IDDR
va disparea
Q
ID PST PDR
Se va afisa in fisierul de iesire minimul elementelor dintre pozitiile PST
si PDR ale vectorului identificat
ID
Date de intrare
Pe prima linie a fisierului
de intrare trains.in se vor gasi
2 numere naturale N si M
reprezentand numarul de vagoane si respectiv numarul de operatii. Pe a doua
linie a fisierului vor exista N
numere intregi cuprinse intre 0
si 32000 reprezentand elementele
vectorului initial. Pe urmatoarele M
linii vor fi descrise operatiile ce trebuiesc simulate, cate una pe fiecare
linie asa cum au fost descrise anterior.
Date de iesire
Fisierul de iesire trains.out
trebuie sa contina M linii cu
cate un numar reprezentand in ordine raspunsul la fiecare operatie de tip Q
din fisierul de intrare.
Restrictii si precizari
2 <= N <= 16000
1 <= M <= 32000
0 <= ID, IDST, IDDR <= 32000
Pozitiile vectorilor
sunt numerotate incepand cu valoarea 1.
La operatia S nu va exista deja
un vector identificat IDDR iar
vectorul cu identificatorul ID
va avea minim pos+1 elemente.
La operatia Q
vom avea 1 <= PST <= PDR <= nr
de elemente ale vectorului ID.