Cod sursa(job #391781)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 6 februarie 2010 12:29:09
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<stdio.h>
#define Nmax 500010
#define Inf 1<<30
int v[Nmax],d[Nmax],p,u,i,k,baza,st,dr,n;

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	
	scanf("%d %d",&n,&k);
	
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	
	baza=-Inf;
	for(p=u=i=1;i<=n;i++)
	{
		while( d[p] <= i-k && p<=u ) p++;
		while( v[d[u]]>v[i] && p<=u) u--;
		
		d[++u]=i;
		
		if(i>=k) 
			if(v[d[p]]>baza) 
			{
				baza=v[d[p]];
				dr=i;
				st=i-k+1;
			}
	}
	
	printf("%d %d %d",st,dr,baza);
	
	return 0;
}