Cod sursa(job #516012)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 22 decembrie 2010 21:51:47
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 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[2500000];
void citire()
{
	fscanf(fin,"%d %d\n",&N,&K);
	fgets(s+1,2500000,fin); s[0]=' ';
	int l=strlen(s),p=0,m=0;
	i=0;
	while(i<=l)
	{
		for(;(s[i]<'0' || s[i]>'9') && i<=l && s[i]!='-';i++);
		if(i>=l) return;
		p++;
		if(s[i]=='-') m=1,i++;
		for(;s[i]>='0' && s[i]<='9';i++)
			v[p]=10*v[p]+s[i]-'0';
		if(m==1) v[p]*=-1,m=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);
}