025 Heapuri

[•AlexandruValeanu]

Poti scoate elementul de pe o pozitie data din heap initializand pozitia aia cu o valoarea mai mica decat radacina, apelezi UpHeap si apoi extragi radacina. Daca vrei sa scoti un element din heap...nu ai cum sa-l cauti in timp logaritmic.

[•jason2013]

Asta-i sursa mea...da raspuns corect si merge si super rapid...nu pot sa-mi dau seama de ce imi da Limit exceeded si Killed by signal 11 si 6.. Un sfat m-ar ajuta enorm..
PS: AM FACUT METODA CU HEAP-URI (TATA / FIU / VEC POZITII)
Cam care e complexitatea codului meu
http://www.infoarena.ro/job_detail/1870456

Cod:

#include<bits/stdc++.h>
using namespace std;

const int NMAX = 200005;
set<int>myHeap;
set<int>::iterator it;
int el[NMAX];
int N, operation, nr;

void citire()
{
    freopen("heapuri.in", "r", stdin);
    freopen("heapuri.out", "w", stdout);
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &operation);
        if(operation == 3) printf("%d\n",*myHeap.begin());
        else if(operation == 2){
            int y; scanf("%d", &y);
            //g<<el[y];
            myHeap.erase(find(myHeap.begin(), myHeap.end(), el[y]) );
        }else{
            int x; scanf("%d", &x);
            myHeap.insert(x);
            el[++nr] = x;
        }
    }
    fclose(stdin);
}

int main()
{
    citire();
    return 0;
}

[•otto1]

Poate sa-mi dea si mie cineva datele de intrare de la testul 2? Am scris 2 programe cu mici diferente intre ele dar care fac in principal aceeasi pasi dar una imi da 30p iar cealalta 100p si vreau sa pot sa le compar si sa deduc diferentele in pasii facuti.

[•AlexandruValeanu]

Le poti downloada de aici: http://www.infoarena.ro/problema/heapuri?action=attach-list

[•otto1]

Multumesc mult pentru teste! cu ele am reusit sa vad unde era eroarea la problema de 30p!