== include(page="template/taskheader" task_id="centru2") ==
Poveste şi cerinţă...
Conducerea oraşului a construit un nou centru pentru conferinţe. $N$ companii şi-au manifestat interesul de a închiria centrul pentru a ţine propriile conferinţe. O companie client doreşte să închirieze centrul doar dacă acesta este disponibil pe întreaga durată a evenimentului. Conducerea oraşului a decis că cea mai bună strategie de închiriere este de a avea cât mai multe companii client. Desigur, vor exista mai multe de moduri de a închiria centrul folosind aceasta strategie. Conducerea oraşului doreşte să reprezinte un model de onestitate şi, din acest motiv, doreşte să aleagă acel set de clienţi care are cardinal maxim şi este minim lexicografic (considerând ordinea în care sunt depuse cererile pentru închiriere).
h2. Cerinta
Determinaţi setul de companii căutat de conducerea oraşului.
h2. Date de intrare
Fişierul de intrare $centru2.in$ ...
Pe prima linie a fişierului de intrare $centru2.in$ se află numărul întreg $N$. Pe următoarele $N$ linii se găsesc câte două numere întregi $a$ şi $b$ separate prin spaţiu, reprezentând momentele de timp între care o companie doreşte să închirieze centrul de conferinţe. Cererile sunt date în ordinea în care au fost depuse.
h2. Date de ieşire
În fişierul de ieşire $centru2.out$ ...
Pe prima linie a fişierului de ieşire $centru2.out$ se găseşte un număr natural $M$, reprezentând cardinalul maxim al unui set de companii client. Pe următoarea linie se găsesc $M$ numere naturale în *ordine crescătoare* ce reprezintă numerele de ordine ale setului de companii ales.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 200 000$
* $1 ≤ a ≤ b ≤ 10^9^$
* Dacă o conferinţă are loc între momentele de timp $a$ şi $b$, atunci se consideră că şi capetele $a$ si $b$ fac parte din conferinţă.
* Pentru $30%$ din teste, $N ≤ 3 000$.
* Un set {$(i{~1~},i{~2~}...i{~M~})$} este mai mic din punct de vedere lexicografic decât un alt set {$(j{~1~},j{~2~}...j{~M~})$} dacă există o poziţie $p$ astfel încât {$i{~p~} < j{~p~}$} si {$i{~1~} = j{~1~}$}, {$i{~2~} = j{~2~}$} ... {$i{~p-1~} = j{~p-1~}$}.
h2. Exemplu
table(example). |_. centru2.in |_. centru2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
3 8
1 5
4 7
7 10
2 4
6 12
9 11
| 2
1 7
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="centru2") ==
