Fişierul intrare/ieşire:proiectoare.in, proiectoare.outSursăONI 2018, clasa a 10-a, ziua 2
AutorAdrian BudauAdăugată deamaliarebAmalia Rebegea amaliareb
Timp execuţie pe test0.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inproiectoare.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?