Cod sursa(job #344166)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 28 august 2009 20:18:55
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
//secventa.cpp
#include <cstdio>
#define DIM 500001
int a[DIM],n,k,p,u,d[DIM],end,i,min;
using namespace std;
void solve()
{   
	p=1;
	min=-300000;
	scanf ("%d%d\n",&n,&k);
	for (i = 1; i <= n; ++i) scanf ("%d",&a[i]);
    for (i = 1; i <= n; ++i)
	{   
		while (p <= u && a[i] <= a[ d[u] ]) --u;
		d[ ++u ] = i;
		if (i - d[p] == k) ++p;
        if (i >= k && a[ d[p] ] > min)
		   {
			   min = a[ d[p] ];
			   end = i;
		   }
	}
printf ("%d %d %d\n",end-k+1,end,min);
}			
int main()
{
	freopen ("secventa.in","r",stdin);
	freopen ("secventa.out","w",stdout);
	solve();
	return 0;
}
//sper sa ne mai vedem...