trains

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

Exemplu

10 14
1 2 3 4 5 6 7 8 9 10
S 0 5 1
Q 1 1 3
J 1 0
Q 1 1 1
Q 1 2 2
Q 1 3 3
Q 1 4 4
Q 1 5 5
Q 1 6 6
Q 1 7 7
Q 1 8 8
Q 1 9 9
Q 1 10 10
Q 1 4 6

6
6
7
8
9
10
1
2
3
4
5
1

Timp maxim de executie/test: 0.2 secunde

Emilian Miron
Facultatea de Matematica-Informatica Bucuresti
emimiron@yahoo.com