Cod sursa(job #187721)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 5 mai 2008 08:16:13
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h> 
#include<string.h>
long p,x,n,k,i=0,st,dr,rez,poz=0,a[500000],q[500000],lung;
char s[350000];
int main(){
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%ld%ld",&n,&k);   
	fgets(s,350000,stdin);   
    lung=strlen(s)-1;   
    while(i<lung){   
        p=1;
		x=0;
		if(s[i]=='-'){
            p=-1;
            ++i;
        }   
        for(;(s[i]!=' ')&&(i<lung);++i)
			x=x*10+s[i]-48;   
        ++poz;   
        a[poz]=x*p;   
        ++i;   
    }
	rez=-500000;
	st=1;
	dr=0;
	for(i=1;i<k;i=i+1){
		while((dr>=st)&&(a[i]<=a[q[dr]]))
			dr=dr-1;
		dr=dr+1;
		q[dr]=i;
	}
	for(i=k;i<=n;i=i+1){
		while((dr>=st)&&(a[i]<=a[q[dr]]))
			dr=dr-1;
		dr=dr+1;
		q[dr]=i;
		while((st<=dr)&&(q[st]<i-k+1))
			st=st+1;
		if(a[q[st]]>rez){
			rez=a[q[st]];
			poz=i;
			}
	}
	printf("%ld %ld %ld\n", poz-k+1,poz,rez);
	fclose(stdin);
	fclose(stdout);
	return 0;
}