Pagini recente » Borderou de evaluare (job #2890022) | Cod sursa (job #2811509)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream cin("heapuri.in");
ofstream cout("heapuri.out");
vector<int>v(1, 0);
vector<int>indice(1,0);
vector<int>ord(1,0);
bool empty()
{
return v.size() == 1;
}
void up(int pos)
{
if(pos >= v.size())
{
return;
}
while(pos > 1 && v[pos] < v[pos / 2])
{
swap(v[pos], v[pos / 2]);
swap(ord[indice[pos]], ord[indice[pos/2]]);
swap(indice[pos], indice[pos/2]);
pos /= 2;
}
}
void down(int pos)
{
while(2 * pos < v.size())
{
int min_fiu = 2 * pos;
if(2 * pos + 1 < v.size() && v[2 * pos + 1] < v[min_fiu])
{
min_fiu = 2 * pos + 1;
}
if(v[min_fiu] >= v[pos])
{
break;
}
swap(v[pos], v[min_fiu]);
swap(ord[indice[pos]], ord[indice[min_fiu]]);
swap(indice[pos], indice[min_fiu]);
pos = min_fiu;
}
}
int main()
{
int t; cin >> t;
int cnt = 0;
for(int i = 0; i < t; i++)
{
char cerinta; cin >> cerinta;
// cout << cerinta << " " << i << "\n";
if(cerinta == '1')
{
int x; cin >> x;
v.push_back(x);
indice.push_back(++cnt);
ord.push_back(v.size() - 1);
up(v.size() - 1);
}
else if(cerinta == '2')
{
int poz; cin >> poz;
int ind = ord[poz];
swap(v[ind], v[v.size() - 1]);
swap(indice[ind], indice.back());
v.pop_back();
indice.pop_back();
up(ind);
down(ind);
}
else
{
cout << v[1] << "\n";
}
}
return false;
}