Antički računar
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 1 s | 1000 Mb | standardni izlaz | standardni ulaz |
Perica je na sajmu antikviteta video jedan specijalan računar. On ima memoriju u koju može da smesti celobrojni niz i ima specijalnu promenljivu n. Kada se računar upali memorija je prazna i n=0. Ovaj računar podržava 2 naredbe:
· ADD x – dodaje broj x u memoriju
· GET – uveća n za jedan i na izlaz ispiše n-ti najmanji on svih brojeva u memoriji
Nažalost Perica nema para da kupi ovaj antički računar pa je zamolio vas da napišete program efikasno izvršava iste naredbe.
Prva linija sadrži dva broja M i N koja predstavljaju broj naredbi ADD, odnosno GET respektivno. U sledecih M redova se nalaze brojevi a[i] koji prestavljaju brojeve koji se dodaju u memoriju tim redom. U narednih N redova se nalaze se nalaze brojevi b[i] koji predstavljaju broj elemenata u memoriji kada smo pozvali naredbu GET. Niz b[i] je uvek sortiran u rastućem poretku.
Izlaz sadrži N linija i svaka predstavlja broj koji je računar dao na izlazu.
1<= M <= 50000
1<= N <= M
-1 000 000 000 <= a[i] <= 1 000 000 000
1<= b[i] <= M
b[i] >= i, i=1..M
b[i] je sortiran u rastućem poretku
Ulaz
izlaz
7 4
3
1
-4
2
8
-1000
2
1
2
6
6
3
3
1
2
Broj naredbe Naredba n Memorija posle naredbe Izlaz
(brojevi su prikazani sortirani)
1 ADD 3 0 3
2 GET 1 3 3
3 ADD 1 1 1, 3
4 GET 2 1, 3 3
5 ADD -4 2 -4, 1, 3
6 ADD 2 2 -4, 1, 2, 3
7 ADD 8 2 -4, 1, 2, 3, 8
8 ADD -1000 2 -1000, -4, 1, 2, 3, 8
9 GET 3 -1000, -4, 1, 2, 3, 8 1
10 GET 4 -1000, -4, 1, 2, 3, 8 2
11 ADD 2 4 -1000, -4, 1, 2, 2, 3, 8
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.