== include(page="template/taskheader" task_id="proiectoare") ==
Primăria a montat, pe faleza din Mamaia, N proiectoare aşezate liniar, pentru fiecare cunoscându-se zona de faleză pe care o luminează, sub forma unui interval $ [ s,d ] $ , unde s şi d (s<d) sunt numere naturalere prezentând distanţele faţă de punctul unde începe faleza. Pentru a verifica eficienţa iluminării falezei, tehnicienii primăriei vor să determine intervalul de faleză de lungime maximă, iluminat de cel mult Kproiectoare, conţinut într-un interval [X,Y]precizat. Pentru afi siguride corectitudinea rezultatelor obţinute, tehnicienii realizeazăQ astfel de verificări.
Primăria a montat, pe faleza din Mamaia, $N$ proiectoare aşezate liniar, pentru fiecare cunoscându-se zona de faleză pe care o luminează, sub forma unui interval $[s,d]$, unde $s$ şi $d (s<d)$ sunt numere naturale reprezentând distanţele faţă de punctul unde începe faleza. Pentru a verifica eficienţa iluminării falezei, tehnicienii primăriei vor să determine intervalul de faleză de lungime maximă, iluminat de cel mult $K$ proiectoare, conţinut într-un interval $[X,Y]$ precizat. Pentru a fi siguri de corectitudinea rezultatelor obţinute, tehnicienii realizează $Q$ astfel de verificări.
Un interval se numeste iluminat de maxim $K$ proiectoare daca este inclus in reuniunea a $K$ sau mai putine proiectoare.
h2. Cerinţă
Dându-se $Q$ intervale de forma $[Xi,Yi]$ determinaţi, pentru fiecare dintre acestea, câte un interval de lungime maximă iluminat de cel mult $K$ proiectoare. Dacă nici un proiector nu iluminează vreo porţiune din intervalul $[Xi,Yi]$ se va afişa valoarea $0$.
h2. Date de intrare
Fişierul de intrare $proiectoare.in$ ...
Datele de intrare se citesc din fişierul text $proiectoare.in$, care are structura următoare:
* pe prima linie se află valorile naturale $N, Q, K$, separate prin câte un spaţiu, cu semnificaţia din enunţ;
* pe următoarele $N$ linii se află câte o pereche de valori naturale $Si, Di$, separate printr-un spaţiu, reprezentând intervalele iluminate de fiecare proiector;
* pe următoarele $Q$ linii se află câte o pereche de valori naturale $Xi,Yi$, separate printr-un spaţiu, reprezentând intervalele pentru care se realizează verificările.
h2. Date de ieşire
În fişierul de ieşire $proiectoare.out$ ...
În fişierul text $proiectoare.out$ se vor scrie $Q$ linii; pe linia $i (1 ≤ i ≤ Q)$ se va scrie un număr natural reprezentând lungimea intervalului obţinut ca răspuns la verificarea efectuată pentru intervalul $[Xi,Yi]$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $0 ≤ S < D ≤ 1 000 000 000$
* $1 ≤ K ≤ N ≤ 100 000$
* $1 ≤ Q ≤ 100 000$
* Pentru teste în valoare de $11$ puncte, $K = 1$ şi $n ≤ 2000$ şi $Q ≤ 2000$
* Pentru teste în valoare de alte $38$ puncte, $K = 1$
* Pentru teste în valoare de alte $21$ puncte, $K = 2$
* Pentru teste în valoare de alte $10$ puncte, $K <= 30$
h2. Exemplu
table(example). |_. proiectoare.in |_. proiectoare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 5 5 1
1 4
2 3
3 6
4 7
4 8
1 10
2 5
3 4
6 8
8 9 | 4
2
1
2
0 |
h3. Explicaţie
...
Pentru verificarea $[1,10]$ cel mai lung interval complet iluminat este $[4,8]$ cu lungimea $4$.
Pentru verificarea $[2,5]$ cele mai lungi intervale complet iluminate sunt $[2,4]$ şi $[3,5]$, ambele au lungimea $2$.
Pentru verificarea $[3,4]$ cel mai lung interval complet iluminat este $[3,4]$ cu lungimea $1$.
Pentru verificarea $[6,8]$ cel mai lung interval complet iluminat este $[6,8]$ cu lungimea $2$.
Pentru verificarea $[8,9]$ se afişează valoarea $0$.
== include(page="template/taskfooter" task_id="proiectoare") ==
