Cod sursa(job #92173)

Utilizator the1dragonIonita Alexandru the1dragon Data 14 octombrie 2007 12:24:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>

int dq[512000], pos[512000];
char si[3072000];
int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	int n, k, i, x, sol=0x80000000, ps, start=1, stop=1, nivel=0, s;
	scanf("%d %d\n", &n, &k);
	gets(si);
	s=1;
	x=0;
	while(si[nivel]!=' ')
	{
		if (si[nivel]=='-')
			s=-1;
		else
		{
			x*=10;
			x+=si[nivel]-'0';
		}
		++nivel;
	}
	x*=s;
	++nivel;
//	printf("%d ", x);
	
	dq[start]=x;
	pos[start]=1;
	for (i=2; i<=n; i++)
	{
		s=1;
		x=0;
		while ((si[nivel]!=' ') && (si[nivel]!=0))
		{
			if (si[nivel]=='-')
				s=-1;
			else
			{
				x*=10;
				x+=si[nivel]-'0';
			}
			++nivel;
		}
		x*=s;
		++nivel;
	//	printf("%d ", x);
		
		while ((pos[start]<=i-k) && (start<=stop)) ++start;
		while ((dq[stop]>=x) && (stop>=start)){ --stop;}
		++stop;
		dq[stop]=x;
		pos[stop]=i;
		if ((dq[start]>sol) && (i>=k))
			{sol=dq[start]; ps=i;}
	}
	printf("%d %d %d", ps-k+1, ps, sol);
	return 0;
}