Cod sursa(job #528904)

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

deque <int> dp,dv;

int main()
{
	int v,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);
		while ((!dp.empty()) && (dv.back()>v))
			dp.pop_back(),dv.pop_back();
		dp.push_back(i);
		dv.push_back(v);
	}
	mx=dv.front();
	y=k;
	for (i=k+1;i<=n;++i)
	{
		scanf("%d",&v);
		while ((!dp.empty()) && (dp.front()<=i-k))
			dp.pop_front(),dv.pop_front();
		while ((!dp.empty()) && (dv.back()>v))
			dp.pop_back(),dv.pop_back();
		dp.push_back(i);
		dv.push_back(v);
		if (dv.front()>mx)
			mx=dv.front(),x=i-k+1,y=i;
			
	}
			
	printf("%d %d %d",x,y,mx);
return 0;
}