Fişierul intrare/ieşire:granita.in, granita.outSursă.campion 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.025 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Granita

La granita statului A cu statul B se afla N dispozitive de aparare. Pentru fiecare dispozitiv k se cunoaste intervalul de lungime [Ak, Bk] in care actioneaza (granita se considera a fi o linie dreapta, iar fiecare dispozitiv acopera un anumit segment de pe aceasta linie). Pentru a reduce costurile de intretinere, presedintele statului A a decis ca unele dintre cele N dispozitive de aparare sa fie desfiintate. Mai precis, vor fi desfiintate dispozitivele redundante. Un dispozitiv i este redundant, daca exista cel putin un alt dispozitiv j, astfel incat intervalul [Ai, Bi] sa fie inclus in intervalul [Aj, Bj] (adica Aj<Ai si Bi<Bj).

Cerinta

Determinati cate dintre cele N dispozitive de aparare sunt redundante.

Date de Intrare

Pe prima linie a fisierului de intrare granita.in se afla numarul intreg N, reprezentand numarul dispozitivelor de aparare. Pe urmatoarele N linii se afla cate doua numere intregi, a si b (a<b), reprezentand capetele intervalelor in care actioneaza fiecare dispozitiv.

Date de Iesire

In fisierul de iesire granita.out contine o singura linie pe care veti afisa un singur numar intreg, reprezentand numarul dispozitivelor redundante.

Restrictii

  • 1 ≤ N ≤ 16.000
  • 0 ≤ Ai < Bi ≤ 2.000.000.000
  • Toate numerele Ai vor fi diferite intre ele
  • Toate numerele Bi vor fi diferite intre ele

Exemple

granita.ingranita.out
5
0 10
2 9
3 8
1 15
6 11
3

Explicatie

Dispozitivele redundante sunt: al doilea, al treilea si al cincilea.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content