Cod sursa(job #2208302)

Utilizator DawlauAndrei Blahovici Dawlau Data 29 mai 2018 01:59:18
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;

class InParser {

	private:
		
		ifstream File;
		static const unsigned int buffSZ = (1 << 15);
		unsigned int buffPos;
		char buff[buffSZ];

		void _advance() {

			if (++buffPos == buffSZ) {

				buffPos = 0;
				File.read(buff, buffSZ);
			}
		}

	public:

		InParser(const char *FileName) {

			File.open(FileName);
			buffPos = buffSZ - 1;
		}

		InParser& operator >>(int &no) {

			int sgn = 1;
			while (!isdigit(buff[buffPos])) {

				if (buff[buffPos] == '-')
					sgn = -1;
				_advance();
			}
			no = 0;
			while (isdigit(buff[buffPos])) {

				no = no * 10 + buff[buffPos] - '0';
				_advance();
			}
			no *= sgn;
			return *this;
		}
};

InParser fin("secventa.in");
ofstream fout("secventa.out");

int main() {

	int N, K;
	fin >> N >> K;

	vector <int> Arr;
	Arr.resize(N + 1);

	for (int idx = 1; idx <= N; ++idx)
		fin >> Arr[idx];

	deque <int> Deque;
	for (int idx = 1; idx < K; ++idx) {

		while (!Deque.empty() && Arr[Deque.back()] > Arr[idx])
			Deque.pop_back();
		Deque.push_back(idx);
	}

	int MaxIdx, Max = -30001;

	for (int idx = K; idx <= N; ++idx) {

		while (!Deque.empty() && Arr[Deque.back()] > Arr[idx])
			Deque.pop_back();
		Deque.push_back(idx);

		if (Max < Arr[Deque.front()]) {

			MaxIdx = idx;
			Max = Arr[Deque.front()];
		}

		while (Deque.front() < idx + 2 - K)
			Deque.pop_front();
	}

	fout << MaxIdx - K + 1 << ' ' << MaxIdx << ' ' << Max;
}