trenuri3

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 statie i . 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, statie i ]. 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 capacitate i .

Î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 $statie{~i~}$ . 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, statie{~i~}]$. 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 $capacitate{~i~}$ .

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

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

h2. Cerinta

h2. Date de intrare

Pe prima linie a fişierului trenuri.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 a i şi b i , separate printr-un spaţiu reprezentând staţiile între care doreşte să circule pasagerul cu numărul i.

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 $a{~i~}$ şi $b{~i~}$ , separate printr-un spaţiu reprezentând staţiile între care doreşte să circule pasagerul cu numărul $i$.

h2. Date de ieşire

Pe prima linie a fişierului trenuri.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.

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$.

h2. Restricţii

* 1 ≤ N, M ≤ 100 000
* 1 ≤ statie i , capacitate i ≤ 1 000 000 000 pentru orice i, 1 ≤ i ≤ N.
* 1 ≤ a i ≤ b i ≤ 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 a i şi să coboare doar la staţia b i .

* $1 ≤ N, M ≤ 100 000$
* $1 ≤ statie{~i~} , capacitate{~i~} ≤ 1 000 000 000$ pentru orice $i, 1 ≤ i ≤ N$.
* $1 ≤ a{~i~} ≤ b{~i~} ≤ 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 $a{~i~}$ şi să coboare doar la staţia $b{~i~}$ .

* 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.

* 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$.

h2. Exemplu

1
2
|

table(example). |_. trenuri3.in |_. trenuri3.out |

| 1 3
10 2
1 5

h3. 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ă.

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