Cod sursa(job #492028)

Utilizator crushackPopescu Silviu crushack Data 13 octombrie 2010 11:27:22
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <deque>
#define NMax 500000

const char IN[]="secventa.in",OUT[]="secventa.out";

int N,K;
int x,y,Max=-1;
int a[NMax];

void solve()
{
	using namespace std;
	int i;
	deque<int> de;
	
	for (i=0;i<N;i++)
	{
		while (!de.empty() && (a[i]<a[de.back()] || i-de.back()>=K))
			de.pop_back();
		de.push_back(i);
		while (!de.empty() && i-de.front()>=K)
			de.pop_front();
		if (i==K-1)
			Max=a[de.front()],x=0,y=K-1;
		if (i>=K && a[de.front()]>Max)
			Max= a[de.front()],x=i-K+1,y=x+K-1;
	}
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&K);
	for (i=0;i<N;i++)
		scanf("%d",a+i);
	fclose(stdin);
	solve();
	
	freopen(OUT,"w",stdout);
	printf("%d %d %d",x+1,y+1,Max);
	fclose(stdout);
	
	return 0;
}