Fişierul intrare/ieşire: | marbles.in, marbles.out | Sursă | preONI 2008, Runda finala |
Autor | Filip Cristian Buruiana | Adăugată de | |
Timp execuţie pe test | 0.125 sec | Limită de memorie | 36864 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Marbles
Gigel are N bilute colorate pe care le aseaza pe axa Ox a unui sistem cartezian de coordonate. Asupra acestora el efectueaza urmatoarele operatii:
- 0 i j va reprezenta o operatie de mutare a bilei aflata la coordonata i la coordonata i+j. Se garanteaza faptul ca intre coordonatele i si i+j nu exista nicio alta bila.
- 1 i j reprezinta operatia de interogare. Astfel, Gigel se intreaba care este numarul maxim de bile de aceeasi culoare care se afla intre coordonatele i si j inclusiv.
Cerinta
Ajutati-l pe Gigel furnizandu-i raspunsurile pentru operatiile de interogare.
Date de intrare
Fisierul de intrare marbles.in contine pe prima linie numerele N si M, numarul de bilute, respectiv numarul de operatii efectuate. Pe urmatoarele N linii se afla cate doua numere intregi ai bi reprezentand coordonata la care se afla initial bila i, respectiv culoarea ei. Urmeaza apoi M linii, fiecare descriind o operatie facuta de Gigel.
Date de iesire
Fisierul de iesire marbles.out va contine pentru fiecare operatie de interogare raspunsul corespunzator.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 100 000
- Culoarea unei bile va fi un numar natural din intervalul [1, 64]
- Coordonatele bilelor la orice moment de timp, precum si toate numerele din fisierul de intrare, vor fi intregi cu semn ce se vor incadra pe 32 de biti.
- Nu vor exista 2 bile la aceeasi coordonata
Exemplu
marbles.in | marbles.out |
---|---|
5 3 1 1 4 1 5 2 11 1 15 3 1 4 13 0 4 -1 1 4 13 | 2 1 |
Explicatie
Initial, intre coordonatele 4 si 13 exista doua bile care sunt colorate cu 1. Dupa mutarea bilei de pe pozitia 4 pe pozitia 4 - 1 = 3, intre coordonatele 4 si 13 mai raman doar doua bile, ambele fiind colorate diferit.