Diferențe pentru problema/stalpi11 între reviziile #2 si #7

== include(page="template/taskheader" task_id="stalpi11") ==

Pe strada principala din oras se gasesc n stalpi de iluminat. Pentru fiecare stalp cunoastem distanta d metri fata de centrul orasului si intensitatea luminoasa a becului cd. Daca d<0 atunci stalpul se gaseste in stanga centrului iar daca d>0 va fi situat in dreapta. Fiecare stalp ilumineaza cd metri in stanga, respectiv cd metri in dreapta. Consideram ca un segment de drum este iluminat daca este acoperit de cel putin un stalp. Determinati numarul numarul maxim de stalpi( $nr_switchoff$ ) care pot fi stinsi astfel incat numarul segmentelor de drum iluminate sa nu se schimbe. Deasemenea primarul orasului doreste sa stie cati metri( $nr_black$ ) de drum aflati intre cel mai din stanga segment iluminat si cel mai din dreapta segment iluminat sunt complet intunecate.

Pe strada principală din oraș se găsesc n stâlpi de iluminat. Pentru fiecare stâlp cunoaștem distanța d, exprimată în metri față de centrul orașului și intensitatea luminoasă a becului cd. Daca d<0, atunci stâlpul se găsește în stânga centrului, iar dacă d>0, va fi situat in dreapta. Fiecare stâlp iluminează cd metri în stânga, respectiv cd metri în dreapta. Considerăm că un segment de drum este iluminat dacă este acoperit de cel puțin un stâlp. Determinați numărul maxim de stâlpi ( $nr_switchoff$ ) care pot fi stinși simultan astfel încât numărul segmentelor de drum iluminate să nu se schimbe. De asemenea, primarul orașului dorește să știe câți metri ( $nr_black$ ) de drum aflați între cel mai din stânga segment iluminat și cel mai din dreapta segment iluminat sunt complet întunecați.

h2. Date de intrare

Fișierul de intrare $stalpi11.in$ contine pe prima linie numarul n iar pe urmatoarele n linii cate doua numere di si cdi reprezentand distanta fata de centrul orasului respectiv intensitatea luminoasa a stalpului i.

Fișierul de intrare $stalpi11.in$ contine pe prima linie numărul n iar pe următoarele n linii câte două numere di și cdi reprezentând distanța față de centrul orașului, respectiv intensitatea luminoasă a stâlpului i.

h2. Date de ieșire

În fișierul de ieșire $stalpi11.out$ vor fi scrise doua numere naturale:nr_switchoff si nr_black

În fișierul de ieșire $stalpi11.out$ vor fi scrise două numere naturale: nr_switchoff si nr_black

h2. Restricții

* $1 ≤ n ≤ 100 000$
* $0 ≤ |di| ≤ 1 000 000 000$
* $1 ≤ cdi ≤ 1 000 000 000$

* $În 30% din teste fiecare segment de drum va fi iluminat de cel mult un stalp$

h2. Exemplu
table(example).
|_. stalpi11.in |_. stalpi11.out |
| 4

2 1

-2 1

8 2
5 1
7 3

| 2 1

| 2 5

|
h3. Explicație

Stalpul 1 acopera segmentul 1 - 3
Stalpul 2 acopera segmentul 6 - 10
Stalpul 3 acopera segmentul 4 - 6
Stalpul 4 acopera segmentul 4 - 10
Observam ca stalpii 2 si 3 pot fi stinsi fara a schimba numarul segmentelor iluminate, deasemenea segmentul 3-4 nu este iluminat si are lungimea de 1m

Stalpul 1 acopera segmentul -3 -- -1
Stalpul 2 acopera segmentul  6 -- 10
Stalpul 3 acopera segmentul  4 -- 6
Stalpul 4 acopera segmentul  4 -- 10
Observam ca stalpii 2 si 3 pot fi stinsi fara a schimba numarul segmentelor iluminate, deasemenea segmentul -1 -- 4 nu este iluminat si are lungimea de 5m

== include(page="template/taskfooter" task_id="stalpi11") ==