Cod sursa(job #158142)

Utilizator coderninuHasna Robert coderninu Data 13 martie 2008 14:32:40
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <values.h>
#define Nmax 510001

struct { int val, poz; } c[Nmax];
char s[Nmax * 30001 + 300001];
int p, u, n, k, x, i, j, rez, prez, ling;


int getval()
{
	int semn, temp=0;
	if (s[j] == '-') { semn = -1; j++; }
	else semn = 1;
	while (s[j] <='9' && s[j]>='0')
	{
		temp = temp*10 + s[j++] - '0';
	}
	j++;
	return temp*semn;
}


int main()
{
	freopen("secventa.in", "r", stdin);
	scanf("%d %d\n", &n, &k);
	gets(s);
	for (p = i = 1, c[0].val=-MAXINT, u = j = 0; i<=k; i++)
	{
		x = getval();
		c[++u].val = x;
		c[u].poz = i;
		while (c[u-1].val >= c[u].val && u-1 >=p)
			c[u-1]=c[u--];
	}
	rez = c[p].val;
	prez = k;


	for (i=k+1; i<=n; i++)
	{
		x = getval();
		c[++u].val = x;
		c[u].poz = i;
		while (c[u-1].val > c[u].val && u-1 >= p)
		{
			c[u-1] = c[u--];
		}
		while (p!=u && c[p].poz + k <= c[u].poz ) p++;
		if (c[p].val > rez)
		{
			rez = c[p].val;
			prez = i;
		}
	}
	fprintf(fopen("secventa.out", "w"), "%d %d %d\n", prez-k+1, prez, rez);
	return 0;
}