Editing 3003 - Intersectie

== Cerința ==
Pe un cerc sunt așezate echidistant N puncte, etichetate în sensul acelor de ceas cu 1, 2, 3, …, N.
Se dau M intervale de forma [a, b] și T interogări de forma P Q.

Pentru fiecare interogare [P, Q] să se verifice dacă este adevărat sau fals că intersecția tuturor intervalelor care au puncte comune cu [P, Q] include intervalul [P, Q].
== Date de intrare ==
Fișierul de intrare intersectie.in conține pe primul rând numerele N, M și T. Pe următoarele M rânduri sunt scrise câte două numere naturale a b, separate prin spațiu, reprezentând capetele celor M intervale date. Pe următoarele T rânduri sunt scrise câte două numere naturale P Q, separate prin spațiu, reprezentând capetele celor T intervale de interogare date.
== Date de ieșire ==
În fișierul de ieșire intersectie.out pe primele T rânduri este scris un număr natural: 1 dacă răspunsul la interogare este adevărat, respectiv 0 dacă răspunsul este fals.
În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."
== Restricții și precizări ==
*2 ≤ N ≤ 1.000.000.000
*1 ≤ M ≤ 100.000
*1 ≤ T ≤ 100.000
*1 ≤ P ≤ N, 1 ≤ Q ≤ N, P și Q sunt etichete date în sensul acelor de ceas
*1 ≤ a ≤ N, 1 ≤ b ≤ N, a și b sunt etichete date în sensul acelor de ceas
Dacă x = y, atunci [x, y] este un interval care conține doar numărul x
Pentru 30% din teste 1 ≤ M ≤ 1000 și 1 ≤ T ≤ 10.000
Pentru 30% din teste 1 ≤ N ≤ 1.000.000
== Exemplu 1 ==
;Intrare
intersectie.in<br>
5 3 3<br>
2 3<br>
5 1<br>
5 5<br>
4 4<br>
3 5<br>
1 1

;Iesire
intersectie.out<br>
0<br>
0<br>
1


== Rezolvare ==
<syntaxhighlight lang="python" line>
def citeste_date():
    with open("intersectie.in", "r") as fin:
        N, M, T = map(int, fin.readline().strip().split())
        intervale = []
        for _ in range(M):
            a, b = map(int, fin.readline().strip().split()))
            intervale.append((a, b))
        interogari = []
        for _ in range(T):
            P, Q = map(int, fin.readline().strip().split()))
            interogari.append((P, Q))
    return N, M, T, intervale, interogari

def include_intervalul(P, Q, start_min, end_max, N):
    if P <= Q:
        if start_min <= P and Q <= end_max:
            return 1
        else:
            return 0
    else:
        if (start_min <= P or Q <= end_max):
            return 1
        else:
            return 0

def verifica_interogari(N, M, T, intervale, interogari):
    rezultate = []
    for P, Q in interogari:
        start_min, end_max = 1, N
        for a, b in intervale:
            if a <= b:
                if a <= Q and P <= b:
                    start_min = max(start_min, a)
                    end_max = min(end_max, b)
            else:
                if a <= Q or P <= b:
                    start_min = max(start_min, a)
                    end_max = min(end_max, b)
        rezultate.append(include_intervalul(P, Q, start_min, end_max, N))
    return rezultate

def scrie_rezultate(rezultate):
    with open("intersectie.out", "w") as fout:
        for rezultat in rezultate:
            fout.write(f"{rezultat}\n")

def main():
    N, M, T, intervale, interogari = citeste_date()
    if not (2 <= N <= 1_000_000_000 and 1 <= M <= 100_000 and 1 <= T <= 100_000):
        print("Datele de intrare nu corespund restricțiilor impuse.")
        return

    rezultate = verifica_interogari(N, M, T, intervale, interogari)
    scrie_rezultate(rezultate)

if __name__ == "__main__":
    main()

</syntaxhighlight>