Cod sursa(job #2191406)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 2 aprilie 2018 19:14:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <cstring>
#include <deque>

using namespace std;

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

int n, k, base = -30005, sizeChars, nr, sizeArray, leftIndex, rightIndex, v[500005];
char s[10000005];
bool sign;
deque < int > positions;

int main()
{
	in >> n >> k;
	in.get();
	in.getline(s + 1, 10000005);
	in.close();

	sizeChars = strlen(s + 1);

	for (int i = 1; i <= sizeChars; i++) {
		if (s[i] == ' ') {
			if (sign) v[++sizeArray] = -nr;
			else v[++sizeArray] = nr;
			nr = 0; sign = 0;
		}
		else {
			if (s[i] == '-') sign = 1;
			else nr = nr * 10 + s[i] - '0';
		}
	}

	if (sign) v[n] = -nr;
	else v[n] = nr;

	for (int i = 1; i <= n; i++) {
		while (!positions.empty() && v[i] < v[positions.back()]) positions.pop_back();
		positions.push_back(i);

		if (positions.front() == i - k) positions.pop_front();

		if (i >= k && base < v[positions.front()]) {
			base = v[positions.front()];
			rightIndex = i;
			leftIndex = i - k + 1;
		}
	}

	out << leftIndex << ' ' << rightIndex << ' ' << base;
	out.close();

    return 0;
}