Cod sursa(job #528908)

Utilizator daniel.florinPitis Daniel-Florin daniel.florin Data 3 februarie 2011 20:04:03
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>
#include <deque>
using namespace std;

deque <int> d;

int main()
{
	int v[50002],i,n,x=1,y,mx=0,k;
	
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d %d",&n,&k);
	for (i=1;i<=k;++i)
	{
		scanf("%d",&v[i]);
		while ((!d.empty()) && (v[d.back()]>v[i]))
			d.pop_back();
		d.push_back(i);
	}
	mx=v[d.front()];
	y=k;
	for (i=k+1;i<=n;++i)
	{
		scanf("%d",&v[i]);
		while ((!d.empty()) && (d.front()<=i-k))
			d.pop_front();
		while ((!d.empty()) && (v[d.back()]>v[i]))
			d.pop_back();
		d.push_back(i);
		if (v[d.front()]>mx)
			mx=v[d.front()],x=i-k+1,y=i;
			
	}
			
	printf("%d %d %d",x,y,mx);
return 0;
}