Cod sursa(job #40428)

Utilizator ZuziFilip Sanziana Zuzi Data 27 martie 2007 13:57:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>

#define NMAX 500001
#define MIN -30001

int n, k, x[NMAX], poz[NMAX], q[NMAX];
int max, msf;

int toint(char s[]) {
	int r, i;
	
	for (r = 0, i = s[0] == '-' ? 1 : 0; s[i] >= '0' && s[i] <= '9'; ++i)
		r = r * 10 + (s[i] - '0');
	
	return s[0] == '-' ? -r : r;
}

void read()
{
	char s[16];
	int i;
	scanf("%s", s);
	n = toint(s);
	scanf("%s", s);
	k = toint(s);
	
	for (i = 1; i <= n; i++) {
		scanf("%s", s);
		x[i] = toint(s);
	}
}

void rezolv()
{
	int i, beg, end;
	beg = end = 1; q[1] = x[1]; poz[1] = 1;
	max = MIN;

	for (i = 2; i <= n; i++)
	{
		if (poz[beg] + k <= i)
			beg++;
			
		for (; x[i] < q[end] && end >= beg; --end);
		q[++end] = x[i], poz[end] = i;
		
		if (i >= k && q[beg] > max)
			max = q[beg], msf = i;
	}	
}

void afisare()
{
	int p;
	for (p = msf - k; p > 0 && x[p] >= max; --p);
	printf("%d %d %d\n", p + 1, msf, max);
}

int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	read();
	rezolv();
	afisare();
	return 0;
}