Fişierul intrare/ieşire:intersectie.in, intersectie.outSursăad-hoc
AutorAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Intersectie

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.

Cerinţă

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.

Restricţii

  • 2 ≤ N ≤ 10^9
  • 1 ≤ M ≤ 10^5
  • 1 ≤ T ≤ 10^5
  • 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 ≤ 10000
  • Pentru 30% din teste 1 ≤ N ≤ 10^6

Exemplu

intersectie.inintersectie.out
5 3 3
2 3
5 1
5 5
4 4
3 5
1 1
0
0
1

Explicaţie

Intervalul [4;4] din interogarea 1 nu se intersecteaza cu nici unul din cele trei intervale date [2;3],[5;1], [5;5]. Răspuns 0.
Intervalul [3;5] din interogarea 2 se intersecteaza cu [2;3],[5;1], [5;5]. Intersecţia acestoa este vidă. Răspuns 0.
Intervalul [1;1] din interogarea 3 se intersecteaza doar cu [5;1]. Intersecţia intervalelor care conţin pe [1;1] este [5;1]. Răspuns 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?