Cod sursa(job #1088970)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 21 ianuarie 2014 02:01:24
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

#define MAXN 500005
int N, K;
int deq[MAXN], front = 1, back = 0;
int sir[MAXN];
char csir[MAXN];

int main()
{
	int i = 0, inceput, sfarsit, maxim = -30005, ind = 0, numar = 0, semn = 1;

	f >> N >> K;
	f.getline(csir, MAXN);
	f.getline(csir, MAXN);

	while (csir[ind] != '\n')
	{
		if (csir[ind] == ' ') {
			sir[++i] = numar * semn;
			semn = 1;
			numar = 0;
		}
		else if (csir[ind] <= '9' && csir[ind] >= '0') {
			numar = (numar * 10) + (int)(csir[ind] - '0');
		}
		else if (csir[ind] == '-') semn = -1;

		ind++;
	}

	for (i = 1; i <= N; ++i)
	{
		while (front <= back && sir[deq[back]] > sir[i])
			back--;
		deq[++back] = i;
		if (deq[front] == i - K)
			front++;
		if (i >= K && sir[deq[front]] > maxim)
			maxim = sir[deq[front]], inceput = i - K + 1, sfarsit = i;
	}

	g << inceput << ' ' << sfarsit << ' ' << maxim;

	return 0;
}