Cod sursa(job #1312269)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 9 ianuarie 2015 08:33:27
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#define DIM 10023
#define NMAX 500023
#define inf -30023
FILE *fin, *fout;
int n, k, temp, st = 1, dr = 0, poz = 0, p, max= inf;
char buff[DIM];
void citeste(int &numar)
{
	numar = 0;
	char semn = '+';
	while(buff[poz] > '9' || buff[poz] < '0')
	{
		semn = buff[poz];
		poz++;
		if(poz == DIM)
		{
			poz = 0;
			fgets(buff, DIM, fin);
		}
	}
	while(buff[poz] >= '0' && buff[poz] <= '9')
	{
		numar = numar*10 + buff[poz] - '0';
		poz++;
		if(poz == DIM)
		{
			poz = 0;
			fgets(buff, DIM, fin);
		}
	}
	if(semn == '-')
	{
		numar = -numar;
	}
}
struct chestie
{
	int val;
	int pos;
} deq[NMAX];
int main()
{
	fin = fopen("secventa.in", "r");
	fout = fopen("secventa.out", "w");
	citeste(n);
	citeste(k);
	for(int i = 0; i< k; i++)
	{
		citeste(temp);
		while(temp < deq[dr].val && dr >= st)
		{
			dr --;
		}
		dr++;
		deq[dr].val = temp;
		deq[dr].pos = i;
	}
	for(int i = k; i< n; i++)
	{
		if(deq[st].pos +k-1 < deq[dr].pos)
		{
			if(deq[st].val > max)
			{
				max = deq[st].val;
				p = deq[dr].pos;
			}
			st++;
		}
		citeste(temp);
		while(temp < deq[dr].val && dr >= st)
		{
			dr --;
		}
		dr++;
		deq[dr].val = temp;
		deq[dr].pos = i;
		if(deq[st].pos +k-1 < deq[dr].pos)
		{
			if(deq[st].val > max)
			{
				max = deq[st].val;
				p = deq[dr].pos;
			}
			st++;
		}
	}
	if(deq[st].val > max)
	{
		max = deq[st].val;
		p = deq[dr].pos;
	}
	fprintf(fout, "%d %d %d\n", p-k+2, p+1, max);
	fclose(fin);
	fclose(fout);
	return 0;
}