Fişierul intrare/ieşire:pcb.in, pcb.outSursăInfoarena Monthly 2014, Runda 9
AutorRadu Stefan VoroneanuAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Problema cu becuri

Nu este doar o pură întâmplare... Antonio chiar s-a gândit la becuri când a conceput această problemă.

Antonio are un şir de N becuri, numerotate de la 1 la N. Iniţial, toate becurile sunt stinse. El are la dispoziţie M comutatoare cu care poate stinge sau aprinde anumite becuri după bunul său plac. Comutatorul i schimbă starea becurilor din intervalul [ A[i], B[i] ] (becurile stinse din acest interval se aprind, iar cele aprinse se sting).

Antonio doreşte să aprindă toate becurile din intervalul [1, X], printr-un număr minim de apăsări ale comutatoarelor pe care le are la dispoziţie. Să se afişeze acest număr minim de apăsări! Dacă acest lucru este imposibil, se va afişa -1.

Date de intrare

Fişierul de intrare pcb.in conţine pe prima linie trei numere naturale N M X, separate între ele prin câte un spaţiu. Pe fiecare linie i din următoarele M linii, se vor găsi două numere naturale A[i] B[i], separate între ele prin câte un spaţiu.

Date de ieşire

În fişierul de ieşire pcb.out se va găsi un singur număr natural, reprezentând numărul minim de apăsări ale comutatoarelor pentru a aprinde toate becurile din intervalul [1, X]. Dacă nu se pot aprinde toate becurile din intervalul [1, X], se va afişa -1.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 200.000
  • 1 ≤ X ≤ N
  • 1 ≤ A[i] ≤ B[i] ≤ N

Exemplu

pcb.inpcb.out
5 3 4
1 3
3 4
3 3
3

Explicaţie

Folosind câte o singură dată fiecare comutator se pot aprinde toate becurile din intervalul [1, 4].

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content