Cod sursa(job #1257098)

Utilizator ade_tomiEnache Adelina ade_tomi Data 7 noiembrie 2014 11:13:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<fstream>
#include<deque>
using namespace std;
int maxi,pozi,n,k,i,x,v[500004];
class InputReader {
	public:
		InputReader() {}
		InputReader(const char *file_name) {
			input_file = fopen(file_name, "r");
			cursor = 0;
			fread(buffer, SIZE, 1, input_file);
		}
		inline InputReader &operator >>(int &n) {
			int semn = 1;
			while(buffer[cursor] < '0' || buffer[cursor] > '9') {
				if (buffer[cursor] == '-') {
					semn = -1;
				}
				advance();
			}
			n = 0;
			while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
				n = n * 10 + buffer[cursor] - '0';
				advance();
			}
			n *= semn;
			return *this;
		}
	private:
		FILE *input_file;
		static const int SIZE = 1 << 17;
		int cursor;
		char buffer[SIZE];
		inline void advance() {
			++ cursor;
			if(cursor == SIZE) {
				cursor = 0;
				fread(buffer, SIZE, 1, input_file);
			}
		}
};


typedef deque<int> deck;
deck q;
int main()
{
	InputReader fin("secventa.in");
	ofstream fout("secventa.out");

	fin>>n>>k;
	maxi=-300001;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
		while(!q.empty() && v[i]<=v[q.back()])
		{
			q.pop_back();
		}
		q.push_back(i);
		if(q.front()==i-k)
			q.pop_front();
		if(v[q.front()]>maxi && i >= k)
		{
			maxi=v[q.front()];
			pozi=i-k+1;
		}
	}
	fout<<pozi<<" "<< pozi+k-1<<" "<<maxi;
	return 0;
}