Fişierul intrare/ieşire:campion.in, campion.outSursăStelele Informaticii 2006, clasele 11-12
AutorMircea Bogdan PasoiAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.1 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Campion

Zaharel lucreaza din greu la site-ul infoarena 2.0. Treaba lui este sa construiasca un sistem de rating al utilizatorilor, in functie de competitiile la care a participat fiecare.

In primul rand, va trebui sa numere cati concurenti au fost campioni pe parcursul timpului. Pentru a simplifica problema, vom considera momentele de timp ca fiind numere reale intre 0 si T.

Fiecare din cei N utilizatori infoarena au inceput sa concureze la timpul 0 si au avut un rating Ri (1 ≤ i ≤ N). Se stie, de asemenea, ca fiecare concurent isi imbunatateste rating-ul cu Di (1 ≤ i ≤ N) pentru fiecare unitate de timp care trece.

Un utilizator se numeste campion daca exista un moment de timp in care a avut cel mai mare rating dintre toti utilizatorii. Daca doi sau mai multi utilizatori au fiecare cel mai mare rating intr-un moment de timp, se considera ca toti sunt campioni.

Cerinta

Ajutati-l pe Zaharel sa determine numarul de utilizatori care au fost campioni.

Date de intrare

In fisierul campion.in se afla pe prima linie numerele naturale N si T reprezentand numarul de utilizatori si limita superioara a momentelor de timp. Urmeaza N linii fiecare continand doua numere naturale Ri Di, reprezentand rating-ul initial si valoarea cu care se imbunatateste per unitate de timp, al fiecarui utilizator.

Date de iesire

Fisierul de iesire campion.out va contine o singura linie pe care se va afla numarul de concurenti care au fost campioni.

Restrictii

  • 1 ≤ N ≤ 20 000
  • 0 ≤ T ≤ 100 000 000
  • 0 ≤ Ri ≤ 1 000 000 000
  • 0 ≤ Di ≤ 1 000 000
  • Rating-ul fiecarui utilizator nu va depasi 2 000 000 000 pentru orice moment de timp din intervalul [0...T]
  • Toatele numerele din fisierul de intrare sunt numere naturale
  • Pot exista utilizatori cu acelasi rating de inceput si aceasi valoare de imbunatatire

Exemplu

campion.incampion.out
3 6
20 0
4 2
15 1
2

Explicatie

Concurentul 1 este initial campion, iar la momentul 5 concurentul 3 devine campion. Concurentul 2 devine campion la momentul 11, dar T = 6, deci nu se ia in considerare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content