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

Cerinta

Determinaţi setul de companii căutat de conducerea oraşului.

Date de intrare

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.

Date de ieşire

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.

Restricţii

  • 1 ≤ N ≤ 200 000
  • 1 ≤ a ≤ b ≤ 109
  • 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 (i1,i2...iM) este mai mic din punct de vedere lexicografic decât un alt set (j1,j2...jM) dacă există o poziţie p astfel încât ip < jp si i1 = j1, i2 = j2 ... ip-1 = jp-1.

Exemplu

centru2.incentru2.out
7
3 8
1 5
4 7
7 10
2 4
6 12
9 11
2
1 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content