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.

Cerință

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 copiiIN.txt 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 ieșire

Fișierul copiiOUt.txt va conține Q linii. Pe fiecare linie se va afla răspunsul la întrebarea respectivă din fişierul de intrare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții

• 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

1
5
8
7
3
10

Explicaţie

După prima mişcare şirul format din numerele preferate ale copiilor devine: 1 5 4 3 2 6 7 8 9 10.

Exemplul 2:

copiiIN.txt

100001
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 nu corespund restrictiilor impuse

Rezolvare

def verificare_restrictii(N, M, Q, updates):
    if not (1 <= N <= 100000 and 1 <= M <= 10000 and 1 <= Q <= 100):
        return False
    for x, y in updates:
        if not (-2000000000 <= x <= 2000000000 and -2000000000 <= y <= 2000000000 and 1 <= x <= y <= N):
            return False
    return True

def main():
    with open("copiiIN.txt", "r") as fin, open("copiiOUT.txt", "w") as fout:
        n = int(fin.readline().strip())
        a = [0] + list(map(int, fin.readline().split()))

        m = int(fin.readline().strip())
        updates = [tuple(map(int, fin.readline().split())) for _ in range(m)]

        q = int(fin.readline().strip())

        if not verificare_restrictii(n, m, q, updates):
            fout.write("Datele nu corespund restrictiilor impuse\n")
            return

        for _ in range(q):
            p = int(fin.readline().strip())
            for j in range(m - 1, -1, -1):
                x, y = updates[j]
                if x <= p <= y:
                    p = x + y - p
            fout.write(str(a[p]) + "\n")

if __name__ == "__main__":
    main()