Cod sursa(job #341346)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 18 august 2009 10:59:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>  
#define N 500002
int n,k,v[N],p,u,maxim,sf,inc,d[N],num;  
char s[N<<3];  
void citire()  
{  
	freopen("secventa.in","r",stdin);  
	freopen("secventa.out","w",stdout);  
	scanf("%d%d\n",&n,&k);  
	fgets(s,N<<3,stdin);  
	int nr=0,semn=1;
	for (int i=0; s[i]&&s[i]!='\n'; ++i)  
	{  
		if (s[i]=='-')  
		{  
			semn=-1; 
			continue;  
		}  
		if(s[i]>='0'&&s[i]<='9')  
		{  
			nr=nr*10+(s[i]-'0');
			continue;
		}  
		v[++num]=nr*semn;
		semn=1;nr=0;
	}  
	v[++num]=nr*semn;
	for (int i=1; i<=k; ++i)     
	{     
		while (p!=u&&v[i]<=v[d[u-1]])     
		 --u;     
		d[u++]=i;     
	}     
	maxim=v[d[p]];     
	inc=1;  
	sf=k;     
	for (int i=k+1; i<=n; ++i)     
	{
		int g=i-d[p];     
		if (g==k)     
		++p;     
		while (u!=p&&v[i]<=v[d[u-1]])     
			--u;     
		d[u++]=i;     
		if (maxim<v[d[p]])     
		{     
			maxim=v[d[p]];     
			inc=i-k+1;     
			sf=i;     
		}     
	}     
	printf("%d %d %d",inc,sf,maxim);     
}     
   
int main()  
{  
 citire();  
 return 0;  
 }