== include(page="template/taskheader" task_id="intersectie") ==
Poveste şi cerinţă...
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$.
h2. 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]$.
h2. Date de intrare
Fişierul de intrare $intersectie.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $intersectie.out$ ...
Î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.
h2. 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$
h2. Exemplu
table(example). |_. intersectie.in |_. intersectie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3 3
2 3
5 1
5 5
4 4
3 5
1 1
| 0
0
1
|
h3. 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.
== include(page="template/taskfooter" task_id="intersectie") ==
