.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » bile2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
bile2


Timp maxim de executie/test:
3 secunde
Memorie totala disponibila/stiva:
32 MB/1 MB

La grãdinita din centrul orasului Suceava existã N copii, numerotati de la 0 la N-1. Primarul le face o vizitã si a hotãrât sã împartã copiilor bilute. Astfel, el are un sac mare plin cu bile ce au inscriptionat pe ele câte un numãr natural. Din când în când primarul mai pune întrebãri copiilor cu privire la bilele pe care le-au primit. Iatã ce operatii poate efectua primarul:
1. dãruieste tuturor copiilor cu numere din intervalul [a,b] câte o bilã inscriptionatã cu numãrul p.
2. îi întreabã care ar fi numãrul inscriptionat pe cea de-a k-a bilã din sirul format din bilele copiilor din intervalul [a,b], stiind cã bilele sunt asezate în ordinea crescãtoare a numerelor inscriptionate pe ele; dacã nu existã k bile în intervalul [a,b], rãspunsul va fi -1.

Cerinta
Ajutati-i pe copii sã rãspundã la întrebãrile primarului.

Date de intrare
Fisierul de intrare bile2.in contine pe prima linie un numãr natural N, reprezentând numãrul de copii. Pe urmãtoarea linie se afla un numãr natural M, reprezentând numãrul de operatii efectuate de primar. Pe urmãtoarele M linii sunt descrise operatiile pe care le efectueazã primarul, câte o operatie pe o linie. O linie care descrie o operatie poate avea unul dintre urmãtoarele douã formate:

Format Explicatie
1 a b p descrie o operatie de tip 1 (primarul va da tuturor copiilor din intervalul [a,b] câte o bilã inscriptionatã cu numãrul natural p).
2 a b k descrie o operatie de tip 2 (primarul îi întreabã pe copii care este numãrul inscriptionat pe cea de-a k-a bilã din sirul format din bilele copiilor din intervalul [a,b], stiind cã bilele sunt asezate în ordinea crescãtoare a numerelor inscriptionate pe ele).

Date de iesire
Fisierul de iesire bile2.out va contine câte o linie pentru fiecare operatie de tipul 2 din fisierul de intrare. Pe cea de-a i-a linie va fi scris un numãr întreg care reprezintã rãspunsul pentru cea de-a i-a operatie de tip 2 din fisierul de intrare.

Restrictii si precizari
1 <= N <= 30000
1 <= M <= 30000
1 <= numerele inscriptionate pe bile <= 30000
Un copil poate avea mai multe bile, eventual de aceeasi valoare.
În urma unei operatii de tip 2, configuratia bilelor rãmâne neschimbatã.
Initial fiecare copil are 0 bile.

Exemplu

bile2.in bile2.out

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

5
2
2
2
-1
2

Daniel Pasaila
Universitatea "Al. I. Cuza" Iasi
Facultatea de Informatica
Contact:danielpasaila@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor