Cod sursa(job #2299465)
| Utilizator |  FMI Bleotiu Cristian bleo16783 |
Data | 9 decembrie 2018 16:48:42 |
|---|---|---|---|
| Problema | Heapuri | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 4.49 kb |
#include <iostream>
#include<fstream>
using namespace std;
int x,y,i,H,j,p,q,k,n,v[200001],h[200001],poz[200001],p2[19];
bool ok;
void ad(int a,int p)
{
v[p]=a;
h[++H]=p;
j=H;
poz[p]=H;
while(v[h[j]]<v[h[j/2]])
{
swap (h[j],h[j/2]);
poz[h[j]]=j;
poz[h[j/2]]=j/2;
j=j/2;
}
//poz[p]=j;
}
/*void el(int p)
{
j=poz[p];
if(j<H)
{
poz[h[H]]=j;
swap(h[j],h[H]);
--H;
while(v[h[j]]>v[h[2*j]])
{
swap(h[j],h[2*j]);
poz[h[j]]=j;
poz[h[2*j]]=2*j;
j=j*2;
}
}
else
--H;
}
*/
void down(int i)
{
ok=0;
while(ok<1)
{
if(2*i+1<H)
{
if(v[h[2*i]]<v[h[2*i+1]])
{
if(v[h[i]]>v[h[2*i]])
{
swap(h[i],h[2*i]);
poz[h[i]]=i;
poz[h[2*i]]=2*i;
i*=2;
}
else
ok=1;
}
else
{
if(v[h[i]]>v[h[2*i+1]])
{
swap(h[i],h[2*i+1]);
poz[h[i]]=i;
poz[h[2*i+1]]=2*i+1;
i=i*2+1;
}
else
ok=1;
}
}
else
{
if(2*i<H)
{
if(v[h[i]]>v[h[2*i]])
{
swap(h[i],h[2*i]);
poz[h[i]]=i;
poz[h[2*i]]=2*i;
i*=2;
}
else
ok=1;
}
else
ok=1;
}
}
}
int main()
{
ifstream f("heapuri.in");
f>>q;
ofstream g("heapuri.out");
p2[0]=1;for(i=1;i<19;++i)p2[i]=2*p2[i-1];
for(p=0;p<q;++p)
{
f>>x;//cout<<p<<'\n';
if(x>2)
{
if(H<2)
{
g<<v[h[1]]<<'\n';
}
else
{
if(H<3)
{
if(v[h[2]]<v[h[1]])g<<v[h[2]]<<'\n';
else
g<<v[h[1]]<<'\n';
}
else
{
if(v[h[2]]<v[h[1]])
{
if(v[h[2]]<v[h[3]])g<<v[h[2]]<<'\n';
else
g<<v[h[3]]<<'\n';
}
else
{
if(v[h[1]]<v[h[3]])
{
g<<v[h[1]]<<'\n';
}
else
{
g<<v[h[3]]<<'\n';
}
}
}
}
}
else
{
f>>y;
if(x<2)
{
++n;
ad(y,n);
}
else
{
//el(y);
j=poz[y];
if(j<H)
{
poz[h[H]]=j;
swap(h[j],h[H]);
//--H;
/*while((2*j<H&&v[h[j]]>v[h[2*j]])||(2*j+1<H&&v[h[j]]>))
{
swap(h[j],h[2*j]);
poz[h[j]]=j;
poz[h[2*j]]=2*j;
j=j*2;
}
*/
if(j>1)
{
swap(h[j],h[j/2]);
poz[h[j]]=j;
poz[h[j/2]]=j/2;
down(j/2);
}
else
down(1);
--H;
}
else
--H;
}
}
}
f.close();
g.close();
return 0;
}
