Cod sursa(job #166753)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 28 martie 2008 14:31:19
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define nmax 500009
int v[nmax],w[nmax],x[nmax]; 
int  n,k,val,min=-nmax,s,in=0,sf=-1;  
char cit[3500014],str[3500024];
void scan()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%d %d\n",&n,&k);
	gets(cit); 
	for(int i=0;i<=n*3;++i)
	{
		if(cit[i]!=' ')
		str[++str[0]]=cit[i];
	}
	for(int i=1;i<=str[0];++i)
	{
		if(str[i]!='-')
		{
			if(str[i-1]=='-')
				x[++x[0]]=-(str[i]-'0');
			else
				x[++x[0]]=str[i]-'0';
		}	
	} 
}
void solve()
{
	for(int i=1;i<=n;++i)  
    {  
        val=x[i];  
        while(in<=sf && w[in]<=i-k)  
            ++in;  
        while(in<=sf && v[sf]>val)  
            --sf;   ++sf;  
        v[sf]=val; w[sf]=i;  
        if(i>=k && v[in]>min)  
        {min=v[in]; s=i;}  
    }  
    printf("%d %d %d\n",s-k+1,s,min);  
}
int main()
{
	scan();
	solve();
	return 0;
}