Cod sursa(job #289468)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 26 martie 2009 19:16:12
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>  
long n,k,p,u;  
char s[3500010];  
long v[500010];  
long deq[500010];  
  
void read()  
{  
	freopen("secventa.in","r",stdin);  
    freopen("secventa.out","w",stdout);  
	scanf("%ld%ld\n",&n,&k);  
	n=0;  
	gets(s);  
	int semn=1,i;  
	long val=0;  
	for(i=0;s[i];i++)  
	{  
		if(s[i]=='-')  
		{  
			semn=-1;  
			continue;  
		}  
		if(s[i]>='0' && s[i]<='9')  
		{  
			val=val*10+(s[i]-'0');  
			continue;  
		}  
		v[++n]=semn*val;  
		semn=1;  
		val=0;  
	}  
	if(s[i-1]!=' ')  
	{  
		v[++n]=semn*val;  
	}  
}  
  
void adauga(long i)  
{  
	while(u>=p && v[deq[u]]>=v[i])  
		u--;  
	deq[++u]=i;  
}  
  
void rez()  
{  
	long i,ci,max=-32001;  
	p=1;  
	u=0;  
	for(i=1;i<k;i++)  
	{
		adauga(i);  
	}  
	for(i=k;i<=n;i++)  
	{  
		adauga(i);
		while(p<=u && deq[p]<i-k+1)
			++p;
		if(v[deq[p]]>max)  
		{  
			max=v[deq[p]];  
			ci=i;
		}
	}  
	printf("%ld %ld %ld\n",ci-k+1,ci,max);  
}  
  
int main()  
{  
    read();  
    rez();  
    return 0;  
}