Fişierul intrare/ieşire:marbles.in, marbles.outSursăpreONI 2008, Runda finala
AutorFilip Cristian BuruianaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.25 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inmarbles.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content