Pagini recente » Cod sursa (job #290209) | Cod sursa (job #2781928) | Cod sursa (job #2450291) | Cod sursa (job #2522617) | Cod sursa (job #779200)
Cod sursa(job #779200)
#include<fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
const int inf=3000001;
int N,K,i,minim,MaxBasis,PozAbsolut,size;
int h[500001],poz[500001];
int v[500002];
void swap(int a, int b)
{int aux=h[a];
h[a]=h[b];
h[b]=aux;
}
void sink(int x)
{int son;
do{son=0;
if(2*x<=size)
{son=2*x;
if((2*x+1)<=size && v[h[2*x+1]]<v[h[2*x]])
son=2*x+1;}
if(son && v[h[x]]>v[h[son]])
{poz[h[x]]=son;
poz[h[son]]=x;
swap(x,son);
x=son;}
else
son=0;
}while(son);
}
void swim(int x)
{int father;
do{father=0;
if(x/2>=1)
father=x/2;
if(father && v[h[father]]>v[h[x]])
{poz[h[x]]=father;
poz[h[father]]=x;
swap(x,father);
x=father;}
else
father=0;
}while(father);
}
int main()
{f>>N>>K;
MaxBasis=-inf;
for(i=1; i<=N; i++)
{f>>v[i];
size++;
h[size]=i;
poz[i]=size;
swim(size);
if(size>K)
{poz[h[size]]=poz[i-K];
swap(poz[i-K],size);
size--;
sink(poz[i-K]);
if(v[h[1]]>MaxBasis)
{MaxBasis=v[h[1]];
PozAbsolut=i;}
}
}
g<<PozAbsolut-K+1<<" "<<PozAbsolut<<" "<<MaxBasis;
f.close();
g.close();
return 0;}