| Fişierul intrare/ieşire: | luffxor.in, luffxor.out | Sursă | PreOJI 2017 |
| Autor | Mihai Popa | Adăugată de |  Popa Mihai •mihaipopa12 |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
LuffXor
Desi nu a terminat inca de numarat muntii din problema precedenta, Bluff a fost strafulgerat de o noua idee de problema. Entuziasmat de noua sclipire, s-a grabit sa o impartaseasca si prietenilor lui. Spre dezamagirea lui Bluff, acestia nu au parut insa prea incantati de descoperirea sa; mai mult, din motive necunoscute, el a fost si poreclit TractoBluff. Ajutati-i totusi pe prietenii lui Bluff sa rezolve problema acestuia pentru a nu se simti inferiori:
Se da V, un multiset (acelasi numar poate aparea de mai multe ori), initial gol, asupra caruia se aplica trei tipuri de operatii:
- O operatie de tip 0, data sub forma (0, x), insereaza numarul x in V;
- O operatie de tip 1, data sub forma (1, x), sterge al x-lea numar inserat in V. Se garanteaza ca operatia este valida: acesta nu a fost deja sters iar x ≤ numarul de inserari facute pana la momentul respectiv. Operatiile de insert sunt indexate incepand cu 1;
- O operatie de tip 2, data sub forma (2, x, k), cere calcularea numarului de elemente y din V, cu proprietatea y xor x ≤ k.
Dandu-se operatiile ce se aplica asupra multisetului V, sa se afle raspunsurile pentru operatiile de tip 2.
Date de intrare
Pe prima linie a fisierului de intrare luffxor.in se afla m, numarul de operatii. Pe urmatoarele m linii se afla operatiile aplicate, cate una pe linie, in ordinea executarii lor, in formatul descris anterior.
Date de ieşire
Fisierul de iesire luffxor.out va contine q linii, unde q este numarul de operatii de tip 2 executate. Raspunsurile vor fi afisate cate unul pe linie.
Restricţii
- m ≤ 200.000
- 1 ≤ toate numerele din fisierul de intrare ≤ 2.000.000.000
- Acelasi poate aparea de mai multe ori in V
- Pentru 30% din teste, m ≤ 10.000
- Pentru alte 10% din teste, toate numerele din fisierul de intrare (in afara de numarul de operatii si indicii operatiilor de stergere) ≤ 100
Exemplu
| luffxor.in | luffxor.out |
|---|---|
| 5 0 1 0 2 2 3 1 1 2 2 3 1 | 1 0 |
