Cod sursa(job #516009)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 22 decembrie 2010 21:42:49
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>
#include <fstream>
using namespace std;
FILE *fin = fopen("secventa.in","r");
FILE *fout= fopen("secventa.out","w");

const int maxn=500010;
int i,N,K,v[maxn],D[maxn],Front,Back,amax,bmax,Max;
char s[1500000];
void citire()
{
	fscanf(fin,"%d %d\n",&N,&K);
	fgets(s,2500000,fin);
	int l=strlen(s),p=0;
	i=0;
	while(i<=l)
	{
		for(;s[i]<'0' || s[i]>'9' && i<=l;i++);
		if(i>=l) return;
		p++;
		for(;s[i]>='0' && s[i]<='9';i++)
			v[p]=10*v[p]+s[i]-'0';
	}
}

int main()
{
	citire();
	Front=1; Back=0;
	for(i=1;i<=N;i++) D[i]=-30001;
	Max=-30001;
	for(i=1;i<=N;i++)
	{
		while(Front<=Back && v[D[Back]] >= v[i])
			Back--;
		D[++Back]=i;
		if(i-K==D[Front]) Front++;
		if(i>=K && v[D[Front]]>Max)
		{
			Max=v[D[Front]];
			amax=i-K+1;
			bmax=i;
		}
	}
	fprintf(fout,"%d %d %d",amax,bmax,Max);
}