| Fişierul intrare/ieşire: | proiectoare.in, proiectoare.out | Sursă | ONI 2018, clasa a 10-a, ziua 2 |
| Autor | Adrian Budau | Adăugată de |  Amalia Rebegea •amaliareb |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
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 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.
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.
Date de intrare
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.
Date de ieşire
Î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].
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
Exemplu
| proiectoare.in | proiectoare.out |
|---|---|
| 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 |
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.
