Cod sursa(job #812779)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 14 noiembrie 2012 14:32:54
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<cstdio>
#include<cstring>
#define maxn 500005


short v[maxn];
int d[maxn];
char buff[maxn*10];
int back,front,sol=-1<<30,l,r;
int n,k,cnt,neg,len;

int get_nr()
{
	neg=1;
	int nr=0;
	for(int i=cnt;i<len;i++)
	{
		if(buff[i]=='-') neg=-1;
		else if(buff[i]>='0' && buff[i]<='9') nr=nr*10+(buff[i]-'0');
		else if(buff[i]==' ') {cnt=i+1;return nr*neg;};
	}
	return nr*neg;
}
	
void read()
{
	freopen("secventa.in","r",stdin);
	scanf("%d %d\n",&n,&k);
	fgets(buff,maxn*10,stdin);
	len=strlen(buff);
	front=1;
	for(int i=1;i<=n;i++)
	{
		v[i]=get_nr();
		while(v[i]<v[d[back]] && front<=back) back--;
		d[++back]=i;
		
		if(v[d[front]]>sol && i>=k) sol=v[d[front]],r=i,l=r-k+1;
		
		if(d[back]-d[front]+1>=k)
		{
			front++;
		}
	}
}

int main()
{
	read();
	freopen("secventa.out","w",stdout);
	printf("%d %d %d",l,r,sol);
}