Cod sursa(job #131994)

Utilizator mihai0110Bivol Mihai mihai0110 Data 4 februarie 2008 20:52:12
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

long n,i,k,max,st,sf,p1,p2;
long a[500001],q[500001],poz[500001];
char *s,cit[10000000];
int main(void)
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%ld%ld",&n,&k);
gets(cit);
gets(cit);
s=cit;
for(i=1;i<n;i++)
		{
		a[i]=atol(s);
		s=strchr(s,' ');
		s++;
		}
		a[n]=atol(s);
max=-32000;
q[1]=a[1];
poz[1]=1;
st=1;
sf=1;
for(i=2;i<=n;i++)
{
	while(st<=sf&&poz[st]<=i-k)
		st++;
	while(st<=sf&&q[sf]>=a[i])
		sf--;
	sf++;
	q[sf]=a[i];
	poz[sf]=i;
	if(i>=k&&q[st]>max)
		{
		max=q[st];
		p2=i;
		p1=p2-k+1;
		}
}
printf("%ld %ld %ld\n",p1,p2,max);
return 0;
}