Cod sursa(job #157784)

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

struct { int val, poz; } c[Nmax];
int p, u, n, k, x, i, rez, prez;



int main()
{
	freopen("secventa.in", "r", stdin);
	scanf("%d %d\n", &n, &k);
	for (p = i = 1, c[0].val=-MAXINT, u = 0; i<=k; i++)
	{
		scanf("%d ", &x);
		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++)
	{
		scanf("%d ", &x);
		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;
}