Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | permking.in, permking.out | Sursă | Finala ONIS 2016 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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
Exemplu
| permking.in | permking.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.
