Fişierul intrare/ieşire:posta.in, posta.outSursăSummer Challenge 2009, Runda 1
AutorDin FolclorAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.175 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Posta

Lance s-a anagajat recent la posta, iar slujba sa consta in sortarea scrisorilor primite. Scrisorile sosesc printr-un dispozitiv special cu mai multe sertare asezate in linie unul dupa altul si numerotate incepand cu 0. Pentru a-si face viata mai usoara, Lance vrea sa cumpere niste vagoane de colectare care sa il ajute sa adune toate scrisorile care sosesc prin dispozitiv. Deoarece este criza, Lance doreste sa minimeze numarul vagoanelor de care are nevoie.

Pentru a se deplasa intre doua sertare consecutive, unui vagon ii este necesara o secunda. Mai mult, la inceputul zilei, Lance poate pozitiona vagoanele oriunde doreste. Stiind ca in total sunt N scrisori, si cunoscand pentru fiecare dintre acestea sertarul si momentul de timp la care soseste, gasiti numarul minim de vagoane de colectare necesare. Trebuie luat in calcul faptul ca Lance doreste ca pentru fiecare scrisoare colectarea sa se faca instantaneu, adica sa existe un vagon in dreptul sertarului in momentul sosirii.

Date de intrare

Fisierul de intrare posta.in contine pe prima linie numarul N al scrisorilor primite. Urmatoarele N linii contin cate 2 numere Si si Ti reprezentand sertarul, respectiv timpul la care soseste cate o scrisoare.

Date de iesire

Pe prima linie a fisierului de iesire posta.out veti afisa un singur numar V, reprezentand numarul minim de vagoane necesare. Pe urmatoarea linie se vor gasi N numere intregi intre 1 si V, reprezentand vagoanele asociate scrisorilor in oridinea din fisierul de intrare.

Restrictii si precizari

  • 1 ≤ N ≤ 100000
  • 0 ≤ Si, Ti ≤ 109
  • Daca exista mai multe solutii poate fi afisata oricare

Exemplu

posta.inposta.out
4
1 1
2 4
3 3
4 1
2
1 2 1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content