Cod sursa(job #569456)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 1 aprilie 2011 15:17:41
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>

using namespace std;

int dr,st=1,d[500001],x[500001],n,k,max1;

ifstream in("secventa.in");
ofstream out("secventa.out");


void eliminast(int i)
{
	if (i-d[st]==k)
		++st;
}

void eliminadr(int i)
{
	while (st<=dr && x[d[dr]]>=x[i])
		--dr;
}
	
void adauga(int i)
{
	d[++dr]=i;
}

int main()
{
	int i,poz;
	in>>n>>k;
	for(i=1;i<=k;++i)
	{
		in>>x[i];
		eliminadr(i);
		adauga(i);
	}
	max1 = x[d[st]];
	poz = k;
	for(i=k+1;i<=n;++i)
	{
		in>>x[i];
		eliminast(i);
		eliminadr(i);
		adauga(i);

		if (x[d[st]]>max1)
		{
			max1=x[d[st]];
			poz=i;
		}
	}
	for(i=poz-k+1;i<=poz;++i)
		out<<x[i]<<" ";
	return 0;
}