Cod sursa(job #716417)

Utilizator teodora.petrisorPetrisor Teodora teodora.petrisor Data 18 martie 2012 19:21:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#define MAX 500001
#include<fstream>
#include<iostream>

using namespace std;

int n, k;
int list[MAX];
int startPos, stopPos, base;

void read()
{
	ifstream inFile("secventa.in");

	inFile>>n;
	inFile>>k;

	for (int i = 1; i<=n; i++)
		inFile>>list[i];

	inFile.close();
}

void print()
{
	ofstream outFile("secventa.out");
	outFile<<startPos<<" "<<stopPos<<" "<<base;

	outFile.close();
}

void solve()
{
	int deque[MAX];

	int left, right;
	left = right = 1;

	deque[1] = 1;
	base = -MAX;


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

		deque[right] = i;
	}

	for (int 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]];
			startPos = i - k + 1;
			stopPos = i;
		}

		if(deque[left] < i - k + 2)
		{
			left ++;
		}
	}
}

int main()
{
	read();
	solve();
	print();

	return 0;
}