Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | centru2.in, centru2.out | Sursă | Summer Challenge 2009, Runda 2 |
| Autor | Din Folclor | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Centru2
Conducerea orasului a construit un nou centru pentru conferinte. N companii si-au manifestat interesul de a inchiria centrul pentru a tine propriile sedinte. O companie client doreste sa inchirieze centrul doar daca acesta este disponibil pe intreaga durata a sedintei. Conducerea orasului a decis ca cea mai buna strategie de inchiriere este de a avea cat mai multe companii client. Desigur, vor exista mai multe de moduri de a inchiria centrul dupa aceasta strategie. Conducerea orasului doreste sa reprezinte un model de onestitate si, de aceea, doreste sa aleaga acel set de clienti care are cardinal maxim si este minim lexicografic (considerand ordinea in care sunt depuse cererile pentru inchiriere).
Cerinta
Determinati setul de companii cautat de conducerea orasului.
Date de intrare
Prima linie a fişierului de intrare centru2.in contine un numarul intreg N. Pe urmatoarele N linii se gasesc cate doua numere a si b separate prin spatiu, reprezentand momentele de timp intre care o companie doreste sa inchirieze centrul de conferinte. Cererile sunt date in ordinea in care au fost depuse.
Date de ieşire
Pe prima linie a fisierului de iesire centru2.out se gaseste un numar natural M, reprezentand cardinalul maxim al unui set de companii client. Pe urmatoarea linie se gasesc M numere naturale in ordine crescatoare ce reprezinta numerele de ordine ale setului de companii ales.
Restricţii
- 1 ≤ N ≤ 200 000
- 1 ≤ a ≤ b ≤ 109
- Daca o sedinta are loc intre momentele de timp a si b, atunci si capetele a si b sunt considerate ca fac parte din sedinta.
Exemplu
| centru2.in | centru2.out |
|---|---|
| 4 4 9 9 11 13 19 10 17 | 2 1 3 |
