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.
de la Paul pentru devil:
1. In heap poti avea o valoare de mai multe ori. Cand o stergi, nu e clar ce se intampla.
2. Fii atent la brutul in N^2 care cauta minimul doar atunci cand stergi elementul minim si restul cazurilor le trateaza O(1).