Cod sursa(job #516452)

Utilizator crazzytudTudor Popa crazzytud Data 24 decembrie 2010 11:07:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
using namespace std;

const int N=500000;

int d[N],v[N],st,dr,k,i,n;

inline void stanga(int i)
{
	if(i-d[st]==k&&v[d[st]]<=v[d[st+1]])
		st++;
}

inline void dreapta(int i)
{
	while(st<=dr && v[d[dr]]>=v[i])
		dr--;
}

inline void adauga(int i)
{
	d[++dr]=i;
}


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

int main()
{
	in>>n>>k;
	int max=0;
	int i1,i2;
	for(i=1;i<=n;i++)
		in>>v[i];
	
	st=1;dr=0;d[1]=1;
	for(i=1;i<=k;i++)
	{
		dreapta(i);
		adauga(i);
	}
	if(v[d[st]] > max)
	{
		i1=d[st];
		i2=d[st]+k-1;
		max=v[d[st]];
	}

	
	for(i=1;i<=n;i++)
	{
		stanga(i);
		dreapta(i);
		adauga(i);
		if(v[d[st]]>max)
		{
			i1=i-k+1;
			i2=i;
			max=v[d[st]];
		}
	}
	out<<i1<<" "<<i2<<" "<<max;
	return 0;
}