Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-07-27 16:34:46.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:centru2.in, centru2.outSursăSummer Challenge 2009, Runda 2
AutorDin FolclorAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.incentru2.out
4
4 9
9 11
13 19
10 17
2
1 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?