Fişierul intrare/ieşire:reborn.in, reborn.outSursăAlgoritmiada 2014, Runda 3
AutorEugenie Daniel PosdarascuAdăugată deedp100Edp100 edp100
Timp execuţie pe test0.8 secLimită de memorie66432 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Reborn

In orasul lui Tsuna sunt N case de mafioti numerotate de la 1 la N, asezate una dupa alta. Reborn are M arme. Pentru fiecare arma i stii intervalul [xi, yi] de case in care Reborn poate sa il omoare pe Tsuna si sa il reinvie in alta casa din acelasi interval. Sa se raspunda la Q intrebari de tipul (a,b): care este numarul minim de arme pe care Reborn trebuie sa le foloseasca astfel incat Tsuna sa poata ajunga din casa a in casa b.

Date de intrare

Fişierul de intrare reborn.in va contine pe prima linie N, M, si Q. Pe urmatoarele M linii vor fi descrise intervalele armelor( linia i + 1 o sa contina elementul xi si yi). Pe urmatoarele Q linii vor fi cate 2 numere a si b reprezentand cele Q intrebari.

Date de ieşire

Fişierul de ieşire reborn.out va contine Q linii, raspunsul pentru fiecare intrebare. Daca nu se poate ajunge din casa a in casa b, se va afisa -1.

Restricţii

  • 1 ≤ N, M, Q ≤ 200.000

Exemplu

reborn.inreborn.out
10 3 6
1 5
4 8
8 9
9 1
1 9
7 10
10 10
3 6
4 6
3
3
-1
0
2
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?