Cod sursa(job #24707)

Utilizator MirageRobert Sandu Mirage Data 3 martie 2007 13:00:53
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<stdio.h>
int main () {
	int n,k,i,st,dr,rez,poz,a[500000],q[500000];
	FILE *in=fopen("secventa.in","r"), *out=fopen("secventa.out","w");
	fscanf(in,"%d%d",&n,&k);
	for(i=1;i<=n;i++)
		fscanf(in,"%d",&a[i]);
	rez=0;
	st=1;
	dr=0;
	for(i=1;i<=k-1;i++){
		while(dr>=st&&a[i]<=a[q[dr]])
			dr=dr-1;
		dr++;
		q[dr]=i;
	}
	for(i=k;i<=n;i++){
		while(st<=dr&&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;
		}
	}
	fprintf(out,"%d %d %d",poz-k+1,poz,rez);
	fclose(in);
	fclose(out);
	return 0;
}