Cod sursa(job #716403)

Utilizator teodora.petrisorPetrisor Teodora teodora.petrisor Data 18 martie 2012 19:04:51
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#define DIM 500001

using namespace std;

int list[DIM], n, k, bPos, fPos, base;

void readFile()
{
	ifstream inFile ("secventa.in");
	inFile>>n>>k;
	for (int i=1;i<=n;i++)
		inFile>>list[i];
	inFile.close();
}

void printFile()
{
	ofstream outFile ("secventa.out");
	outFile<<bPos<<" "<<fPos<<" "<<base<<endl;
	outFile.close();
}

void detSol()
{
	int right,left,i,deque[DIM];

	left=right=1;
	deque[1]=1;
	base=-DIM;

	for (i=2; i < k; i++)
	{
		while (list[deque[right]]>=list[i]&&right>=left)
			right--;

		right++;
		deque[right]=i;
	}
	for(i=k;i<=n;i++)
	{
		while (list[deque[right]]>=list[i]&&right>=left)
			right--;

		right++;
		deque[right]=i;

		if (list[deque[left]]>base)
		{
			base=list[deque[left]];
			bPos=i-k+1;
			fPos=i;
		}
		if (deque[left]<i-k+2)
			left++;
	}
	}

int main()
{
	readFile();
	detSol();
	printFile();
	return 0;
}