Fişierul intrare/ieşire:trenuri3.in, trenuri3.outSursăONI 2015 Clasele 11-12
AutorEugenie Daniel PosdarascuAdăugată deassa98Andrei Stanciu assa98
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trenuri3

Gara de Nord este cea mai vestită gară din lume. Japonezii, invidioşi pe sistemul performant de întârziere al trenurilor din Gara de Nord, s-au hotărât să analizeze motivul realizării unei astfel de performanţe.

În Gara de Nord (considerată staţia 0) există N trenuri. Pentru fiecare tren i ştim că va pleca din Gara noastră protagonistă (staţia 0) şi o să meargă până la staţia statiei . Staţiile x şi x+1 sunt legate în mod direct pentru orice x, astfel că trenul i va opri în toate staţiile din intervalul [0, statiei]. De asemenea, ştim că trenul i are o capacitate egală cu numărul maxim de oameni pe care îl poate transporta. Această capacitate este notată cu capacitatei .

Avem M pasageri dornici sa folosească magnificul traseu. Pentru fiecare pasager i ştim intervalul de statii [ai, bi] pe care vrea să îl parcurgă. Mai exact, acesta vrea să se urce într-un tren în staţia ai şi să coboare în staţia bi .

Cerinta

Din cauza capacităţii limitate a trenurilor, este posibil ca nu toţi pasagerii sa poată obţină un loc şi să ajungă în destinaţia dorită. Să se determine numărul maxim de pasageri care pot ajunge din staţia de plecare în staţia de sosire, precum şi o configuraţie în care aceştia se pot urca în trenuri.

Date de intrare

Pe prima linie a fişierului trenuri3.in se află 2 numere naturale N şi M, separate printr-un spaţiu, cu semnificaţia din enunţ. Următoarele N linii vor descrie cele N trenuri. Pe linia i + 1 se vor afla două valori întregi separate prin câte un spaţiu: statie i şi capacitate i care descriu trenul cu numărul i. Urmatoarele M linii vor descrie itinerariile celor M pasageri. Astfel, pe linia N + i + 1 se vor afla două valori întregi ai şi bi , separate printr-un spaţiu reprezentând staţiile între care doreşte să circule pasagerul cu numărul i.

Date de ieşire

Pe prima linie a fişierului trenuri3.out se va afişa un număr natural P, reprezentând numărul maxim de pasageri care pot să îşi realizeze traseul propus. Pe următoarele M linii se vor afişa M numere naturale. Astfel, pe linia i + 1 se va afişa trenul în care va urca pasagerul i. Dacă pasagerul i nu poate să se urce în niciun tren, se va afişa valoarea 0.

Restricţii

  • 1 ≤ N, M ≤ 100 000
  • 1 ≤ statiei , capacitatei ≤ 1 000 000 000 pentru orice i, 1 ≤ i ≤ N.
  • 1 ≤ ai ≤ bi ≤ 1 000 000 000 pentru orice i, 1 ≤ i ≤ M.
  • Un pasager nu poate să coboare dintr-un tren şi să ia alt tren. Pasagerul i poate să urce doar în staţia ai şi să coboare doar la staţia bi .
  • Pot exista mai multe soluţii pentru repartizarea pasagerilor în trenuri. Orice soluţie cu număr maxim de pasageri posibil va obţine punctaj maxim.
  • Pentru afişarea numărului corect de pasageri se va acorda 30% din punctajul pe un test.
  • Pentru 20% din teste N = 1.
  • Pentru 60% din teste N, M ≤ 2000.
  • Trenurile sunt indexate de la 1 la N.

Exemplu

trenuri3.intrenuri3.out
2 3
10 1
15 1
2 8
7 10
8 13
3
2
1
2
1 3
10 2
1 5
3 7
4 9
2
1
0
1

Explicaţie

In primul exemplu primul şi ultimul pasager vor urca în trenul 2, iar pasagerul 2 în trenul 1.
Dacă pasagerul 1 s-ar fi urcat în trenul 1, ar fi trebuit sa alegem care dintre pasagerul 2 şi 3 să se urce în trenul 2 deoarece cele 2 itinerarii se intersectează, iar cei doi pasageri nu ar avea loc în acelaşi tren.

In al doilea exemplu orice combinaţie în care selectăm 2 din cei 3 pasageri se consideră validă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?