Fişierul intrare/ieşire:	heapuri.in, heapuri.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.125 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Heapuri

Se da o multime de numere cu N elemente. Se cere sa se efectueze M operatii asupra acestei multimi astfel. Operatiile sunt de 3 tipuri:

• Operatia de tipul 1: inserareaza elementul x in multime
• Operatia de tipul 2: stergerea elementului x din multime
• Operatia de tipul 3: care este elementul minim din multime

Date de intrare

Fisierul de intrare heapuri.in va contine pe prima linie numarele N si M. Pe a doua linie se vor afla N numere, reprezentand multimea initiala. Pe liniile 3 .. M+2 se vor afla operatiile descrise astfel: un numar cod reprezentand tipul operatiei, iar in caz ca acesta este 1 sau 2 se mai da si un numar x avand semnificatia din enunt.

Date de ieşire

Fisierul de iesire heapuri.out va contine pe cate o linie raspunsul pentru fiecare operatie de tipul 3 din fisierul de intrare.

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 100 000
• Elementele multimii nu vor depasi 1 000 000 000

Exemplu

Explicaţie

La prima operatie de tipul 3 multimea arata astfel: {4, 9, 7, 12}
La a doua operatie de tipul 3 multimea arata astfel: {2, 9, 7 12}
la a treia operatie de tipul 3 multimea arata astfel: {9, 7, 12}

Cum se trimit solutii?

Indicatii de rezolvare

Problema se poate rezolva brut-force tinand numerele intrun vector, si efectuand pur si simplu fiecare operatie. Aceasta solutie are complexitate O(1) pe o operatie de tipul 1 si O(N) pe celelalte si nu ar trebui sa ia ~30 de puncte.

Rezolvarea optima se face folosind un heap, care suporta aceste efectuarea operatiilor de tipul 1 si 2 in O(log N) si a operatiilor de tipul 3 in O(1).
Pentru detalii despre cum se implementeaza un heap si ce este acesta puteti citi aici.

catre Paul si buru: nu va speriati o sa pun in seara asta si testele si sursa, scuze ca am trecut peste deadline. My bad.
Paul:
1. Fii atent la brutul in N^2 care cauta minimul doar atunci cand stergi elementul minim si restul cazurilor le trateaza O(1).
2. Nu uita ca se poate face si in sqrt (tii pentru fiecare bucata de sqrt(N+M) minimul) si adaugi bucati pe parcurs.
3. Explica ca lumea cum se face un heap.
4. Baga probleme suplimentare / aplicatii. Explica in ce alte situatii e bun un heap (ex. Dijkstra, Prim).
Cosmin:
De ce e multime si nu colectie de elemente. Nu imi place ca adaugi o restrictie care nu e necesara la heapuri prin faptul ca zici ca elementele apartin unei multimi.
devil
Cand am zis multime ma gandeam mai mult la faptul ca intr-o multime nu poate exista acelasi element de 2 ori. Am uitat insa acest lucru pe parcurs si am uitat sa precizez ca daca un element e deja in heap nu mai intra inca o data si de asemenea am uitat sa pun elementele mai mici ca 100000 ca sa se poate verifica usor acest lucru.