Fişierul intrare/ieşire:permking.in, permking.outSursăFinala ONIS 2016
AutorEugenie Daniel PosdarascuAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Permking

Regele permutarilor a dat zvon in toata tara si si-a facut cunoscuta intreaga putere: "Mie nu imi e frica decat de propria-mi putere!!!"

Fie o permutare P de lungime N. Asupra acestei permutari se executa M operatii de tipul a, b: sorteaza in ordine crescatoare toate elementele din intervalul [a,b]. La finalul celor M operatii, permutarea este considerata sortata daca toate elementele apar in ordine strict crescatoare (ramane exercitiu de imaginatie cum arata o permutare sortata).

Dandu-se M si cele M operatii, sa se raspunda cu 1 daca operatiile sunt suficiente sa sorteze ORICE permutare P existenta de lungime N si cu 0 daca nu.

Date de intrare

Fişierul de intrare permking.in va contine un numar natural T reprezentand numarul de teste. Pe urmatoarele linii sunt cele T teste in urmatorul format: pe prima linie se afla 2 numere naturale N si M. Pe urmatoarele M linii sunt cate 2 numere naturale a, b reprezentand cele M operatii.

Date de ieşire

Fişierul de ieşire permking.out va contine T linii, pe linia x aflandu-se raspunsul pentru testul i (0 sau 1).

Restricţii

  • 1 ≤ T ≤ 20
  • 1 ≤ N, M ≤ 1000
  • 1 ≤ a ≤ b ≤ N

Exemplu

permking.inpermking.out
2
2 1
1 2
3 1
1 2
1
0

Explicaţie

In primul caz, atat permutarea (1, 2), cat si permutarea (2, 1) sunt sortate corect. In al doilea caz, permutarea (2, 3, 1) nu este sortata corect.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?