Cod sursa(job #24743)

Utilizator paulDeac Adrian paul Data 3 martie 2007 15:19:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<fstream.h>
#include<values.h>

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

int main()
{
	long long n,k,i,st,dr,rez,poz,a[15000],q[15000];
	in>>n>>k;
	for(i=1;i<=n;i++)
		in>>a[i];
	rez=-32000;
	st=1; dr=0;
	for(i=1;i<=k-1;i++)
	{
		while(dr>=st && a[i]<=a[q[dr]])
			dr=dr-1;
		dr=dr+1;
		q[dr]=i;
	}
	for(i=k;i<=n;i++)
	{
		while(st<=dr && a[i]<=a[q[dr]])
			dr=dr-1;
		dr=dr+1;
		q[dr]=i;
		while(st<=dr && q[st]<i-k+1)
			st=st+1;
		if(a[q[st]]>rez)
		{
			rez=a[q[st]];
			poz=i;
		}
	}
	out<<poz-k+1<<" "<<poz<<" "<<rez;
	return 0;
}