Fișierul intrare/ieșire stalpi11.in, stalpi11.out Sursă Olimpiada pe scoala 2016 clasele 11/12
Autor Bogdan Marin Adăugată de avatar bogdanmarin69 Bogdan Marin bogdanmarin69
Timp de execuție pe test 0.25 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Stalpi11 (clasele 11 și 12)

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.

Date de intrare

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.

Date de ieșire

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

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

Exemplu

stalpi11.in stalpi11.out
4
-2 1
8 2
5 1
7 3
2 5

Explicație

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii