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
5 3 3
2 3
5 1
5 5
4 4
3 5
1 1

Iesire

intersectie.out
0
0
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>