Cod sursa(job #27525)

Utilizator devilkindSavin Tiberiu devilkind Data 6 martie 2007 14:52:58
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <stdio.h>
#include <string.h>
#define filein "secventa.in"
#define fileout "secventa.out"
#define NMax 500001
#define NMaxS 3000002
typedef char string[NMaxS + 10];
typedef struct {
				 int poz;
				 int V;
			   }entry ;

int n, k;
string S;
int v[NMax + 1];

entry Q[NMax + 1];

int MAX, prim;


void citire()
{
	FILE *fin = fopen(filein, "r");
	int i, nr = 0, x = 0, len, sign = 1, ok = 0;

		fscanf(fin, "%d %d", &n, &k);
		fgets(S, 10, fin);
		fgets(S, NMaxS, fin);

		len = strlen(S);
		for (i = 0; i < len; i++)
			if (S[i] == '-')
				sign = -1;
			else if (S[i] >= '0' && S[i] <= '9')
			{
				x = x * 10 + (S[i] - '0');
				ok = 1;
			}
			else if (ok)
			{
				v[++nr] = x * sign;
				x = 0; sign = 1;
				ok = 0;
			}

		if (ok)
			v[++nr] = x * sign;


	fclose(fin);
}

void compute()
{ int i, last = 1, first = 1;


	MAX = -30001;

	Q[1].poz = 1; Q[1].V = v[1];
	for (i = 2; i <= n; i++)
	{
		while (first <= last && Q[first].poz <= i-k) first++;
		while (last >= first && Q[last].V >= v[i])   last--;

		Q[++last].poz = i;
		Q[last].V = v[i];

		if (i >= k)
		{
			if (Q[first].V > MAX)
			{	MAX = Q[first].V; prim = i; }

		}

	}

}

void print()
{
	FILE *fout = fopen(fileout, "w");

		fprintf(fout, "%d %d %d\n", prim-k+1, prim, MAX);

	fclose(fout);
}

	FILE *fout,*fin;
int i, nr = 0, x = 0, len, sign = 1, ok = 0;
int last = 1, first = 1;

int main()
{
//	citire();
fout = fopen(fileout, "w");
fin = fopen(filein, "r");


		fscanf(fin, "%d %d", &n, &k);
		fgets(S, 10, fin);
		fgets(S, NMaxS, fin);

		len = strlen(S);
		for (i = 0; i < len; i++)
			if (S[i] == '-')
				sign = -1;
			else if (S[i] >= '0' && S[i] <= '9')
			{
				x = x * 10 + (S[i] - '0');
				ok = 1;
			}
			else if (ok)
			{
				v[++nr] = x * sign;
				x = 0; sign = 1;
				ok = 0;
			}

		if (ok)
			v[++nr] = x * sign;


	fclose(fin);




//	compute();




	MAX = -30001;

	Q[1].poz = 1; Q[1].V = v[1];
	for (i = 2; i <= n; i++)
	{
		while (first <= last && Q[first].poz <= i-k) first++;
		while (last >= first && Q[last].V >= v[i])   last--;

		Q[++last].poz = i;
		Q[last].V = v[i];

		if (i >= k)
		{
			if (Q[first].V > MAX)
			{	MAX = Q[first].V; prim = i; }

		}

	}



//	print();



		fprintf(fout, "%d %d %d\n", prim-k+1, prim, MAX);

	fclose(fout);

	return 0;
}