Fişierul intrare/ieşire:carray.in, carray.outSursăLot Alba Iulia 2010, Baraj 2
AutorMugurel Ionut AndreicaAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test0.7 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Carray

Un vector este o secvenţă de numere naturale. Iniţial se dau N vectori, numerotaţi de la 1 la N, fiecare din ei conţinând câte un singur număr natural. Apoi se definesc alţi M vectori (numerotaţi de la N+1 la N+M). Vectorul i (N+1≤i≤N+M) se obţine prin concatenarea vectorilor cu numerele a(i) şi b(i). Prin concatenare înţelegem adăugarea elementelor lui b(i), în ordine, după ultimul element din a(i). În urma concatenării vectorii a(i) şi b(i) nu se modifică (practic, doar se creează un vector nou fără modificarea vectorilor existenţi).

Considerând cei N+M vectori definiţi anterior, trebuie să răspundeţi la Q întrebări de tipul (i,p), având semnificaţia:
Care este numărul de pe poziţia p din vectorul cu numărul i ? Numerele dintr-un vector sunt numerotate de la 1 la numărul de elemente din cadrul vectorului.

Date de intrare

Prima linie a fişierului de intrare carray.in conţine trei numere naturale: N, M şi Q. Următoarele N linii conţin fiecare câte un număr natural. Numărul de pe a i-a dintre aceste linii reprezintă numărul conţinut în vectorul i. Următoarele M linii conţin fiecare câte două numerele naturale. A i-a dintre aceste M linii conţine valorile a(N+i) şi b(N+i) (pe baza cărora se construieşte vectorul N+i). Următoarele Q linii conţin fiecare câte două numere naturale i şi p, reprezentând o întrebare (i,p).

Date de ieşire

În fişierul de ieşire carray.out veţi afişa, în ordine, pentru fiecare întrebare (i,p) din fişierul de intrare, numărul care se află pe poziţia p din vectorul i.

Restricţii

  • 1 ≤ N ≤ 20 000
  • 0 ≤ M ≤ 500 000
  • 1 ≤ Q ≤ 20 000
  • 1 ≤ a(i) < i şi 1 ≤ b(i) < i (pentru N+1 ≤ I ≤ N + M)
  • În teste, numărul de elemente ale fiecărui vector va fi cel mult egal cu 1016.
  • Argumentul i al unei întrebări (i, p) este cuprins între 1 şi N+M.
  • Argumentul p al unei întrebări (i, p) este cuprins între 1 şi numărul de elemente din vectorul i.
  • Numărul natural conţinut de fiecare din vectorii 1,...,N este între 0 şi 100 000 000.

Exemplu

carray.incarray.out
3 4 5
3
6
9
1 2
4 2
5 5
6 3
1 1
4 2
5 2
6 4
7 6
3
6
6
3
6

Explicaţie

Vectorii 4, 5, 6 şi 7 conţin următoarele elemente, in ordine:

  • vectorul 4: 3, 6
  • vectorul 5: 3, 6, 6
  • vectorul 6: 3, 6, 6, 3, 6, 6
  • vectorul 7: 3, 6, 6, 3, 6, 6, 9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content