Cod sursa(job #187722)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 5 mai 2008 08:37:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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[3500000];   
int main(){
        freopen("secventa.in","r",stdin);   
        freopen("secventa.out","w",stdout);   
        scanf("%ld %ld\n", &n, &k);   
        fgets(s,3500000,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=-2000000000;   
	st=1;   
	dr=0;   
	for(i=1;i<k;i++){
		while((dr>=st) && (a[i]<=a[q[dr]]))
			dr=dr-1;
		dr=dr+1;   
		q[dr]=i;
	}   
	for(i=k;i<=n;i++){
		while((dr>=st)&&(a[i]<=a[q[dr]]))
           dr--;
		dr++;   
		q[dr]=i;   
		while((st<=dr)&&(q[st]<i-k+1))
           st++;   
		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;
}