0144 - copii

Enunt

În Bistriţa sunt N copii, fiecare dintre ei având un număr preferat Xi . Copii se aşează pe un rând, cu poziţiile numerotate de la 1 la N. După ce copii s-au aşezat, profesoara de educaţie fizică le cere să execute M mişcări de tipul (a, b), cu semnificaţia că îşi vor schimba ordinea copiii care se află între poziţiile a şi b, inclusiv.

Cerinta

Să se răspundă la Q întrebări de tipul p, cu semnificaţia: care este numărul preferat al copilului, care se află pe poziţia p, după executarea mişcărilor cerute de profesoara de educaţie fizică.

Date de intrare

Fișierul copii.in are pe prima linie un număr natural N. Pe linia a 2-a sunt N numere Xi , separate prin câte un spațiu, cu semnificaţia din enunţ. Pe linia a 3-a este numărul M. Pe următoarele M linii se găseșc câte un două numere a şi b cu semnificația de mai sus. Pe următoarea linie se află numărul Q. Pe următoarele linii se află câte un număr p, cu semnificaţia de mai sus.

Date de iesire

Fișierul copii.out va conține Q linii. Pe fiecare linie se va afla răspunsul la întrebarea respectivă din fişierul de intrare

Restricții si precizari

1 ≤ N ≤ 100.000
1 ≤ M ≤ 10.000
1 ≤ Q ≤ 100
1 ≤ a ≤ b ≤ N
-2.000.000.000 ≤ Xi ≤ 2.000.000.000

Exemplul 1

copiiin.txt

10

1 2 3 4 5 6 7 8 9 10

2

2 5

4 8

6

1

2

4

5

8

10

copiiout.txt

Datele introduse corespund restrictiilor impuse.

c

Exemplul 2

copiiin.txt

0

-23 -2 -4 0 5 32 2 9 8 2

-1

4

99

-6

7

copiiout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

def numar_preferat_dupa_misari(N, M, preferinte, misari, Q, intrebari):

   # Inițializăm ordinea copiilor
   ordine = list(range(1, N + 1))

   # Aplicăm mișcările
   for misare in misari:
       a, b = misare
       ordine[a - 1:b] = sorted(ordine[a - 1:b])

   # Răspundem la întrebările de tipul p
   rezultate = []
   for intrebare in intrebari:
       p = intrebare
       numar_preferat = preferinte[ordine[p - 1] - 1]
       rezultate.append(numar_preferat)

   return rezultate

print(rezultate)

</syntaxhighlight>