Lungimi de interval

linterv

==Include(page="template/taskheader" task_id="linterv")==

== include(page="template/taskheader" task_id="linterv") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| linterv.in | linterv.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="linterv") ==

==Include(page="template/raw")==
 
Lungimi de interval
 
 
 
Se dau N intervale [A[i],B[i]] (1<=i<=N). Calculati suma lungimilor tuturor intervalelor. Intervalele care se suprapun se vor lua in considerare o singura data.
 
h2. Date de Intrare (fisier: linterv.in)
 
Fisierul de intrare va contine mai multe teste. Pe prima linie se va afla T numarul de teste. Pe prima linie a fiecarui test se va afla N - numarul de intervale, urmand N linii cu cate doua numere A[i] si B[i] - capetele intervalelor.
 
h2. Date de Iesire (fisier: linterv.out)
 
Fisierul de iesire va contine T linii pe fiecare aflandu-se un singur numar x - suma calculata.
 
h2. Restrictii
 
. 1 <= N <= 5.000
 
. -1.000.000 <= A[i] <= B[i] <= 1.000.000
 
. 1 <= T <= 75
 
h2. Exemplu
 
linterv.in linterv.out
1 18
 
6
 
-5 5
 
0 3
 
2 8
 
10 13
 
11 15
 
100 100
 
 
 
 
==Include(page="template/taskfooter" task_id="linterv")==