| Fişierul intrare/ieşire: | prieteni2.in, prieteni2.out | Sursă | FMI No Stress 10 |
| Autor | Stefan Radu | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Prieteni2
Moş Crăciun a vrut să facă un experiment anul acesta, aşa că a adunat n oameni şi i-a înşirat într-o linie. Se ştie că în această perioadă a anului se petrec trei tipuri de evenimente stranii.
- 1 i - omul i se împrieteneşte (ca prin minune) cu omul i + 1
- 2 i - omul i strică prietenia cu omul i + 1 (un comportament neînţeles)
- 3 a b - Moş Crăciun se întreabă care este cel mai lung şir de prieteni din intervalul [a, b]
Moş Crăciun a încercat să îşi răspundă la întrebări, dar bătrâneţea îşi spune cuvântul. În final vă cere vouă să îl ajutaţi.
Date de intrare
Fişierul de intrare prieteni2.in va conţine pe prima linie numărul n, iar pe a doua linie numărul q. Următoarele q linii vor descrie fiecare câte un eveniment.
Date de ieşire
Fişierul de ieşire prieteni2.out va conţine răspunsurile pentru evenimentele de tip 3, fiecare pe câte o linie.
Restricţii
- pentru 40% din punctaj 1 ≤ n, q ≤ 3000
- pentru alte 30% din punctaj 1 ≤ n, q ≤ 30000
- pentru alte 30% din punctaj 1 ≤ n, q ≤ 200000
- pentru evenimente de tip 1 se garantează că 1 ≤ i < n şi că i nu e prieten cu i + 1
- pentru evenimente de tip 2 se garantează că 1 ≤ i < n şi că i e prieten cu i + 1
- pentru evenimente de tip 3 se garantează că 1 ≤ a, b ≤ n
Exemplu
| prieteni2.in | prieteni2.out |
|---|---|
| 3 11 3 1 3 1 1 3 1 3 3 2 3 1 2 3 1 3 3 1 2 3 2 3 3 2 2 2 1 3 1 3 | 1 2 1 3 2 2 1 2 |
| 3 4 1 2 3 1 3 2 2 3 2 3 | 2 1 |
Explicaţie pentru exemplul 2
- 2 se împrieteneşte cu 3
- cel mai lung lanţ dintre 1 şi 3 este 2-3, de lungime 2
- 2 se supără cu 3
- cel mai lung lanţ dintre 2 şi 3 este de lungime 1 (doar 2, sau doar 3).
Trebuie sa te autentifici pentru a trimite solutii. Click aici
