Cod sursa(job #1607477)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 21 februarie 2016 11:26:35
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector <int> v;
deque <int> dq;
int N, K;

int main()
{
	int _end = 0;
	int _max = -(1<<30);
	int base = 0;
	fin >>N >>K;
	v.resize(N+1);
	for (int i = 1; i <= N; ++i)
		fin >>v[i];
	dq.push_back(1);
	for (int i = 2; i <= N; ++i)
	{
		while (!dq.empty() && dq.front() < i - K + 1)
			dq.pop_front();
		while (!dq.empty() && v[dq.back()] > v[i])
			dq.pop_back();
		dq.push_back(i);
		if (i >= K)
		{
			base = dq.front();
			if (v[base] > _max)
			{
				_max = v[base];
				_end = i;
			}
		}
	}
	fout <<_end - K + 1 <<' ' <<_end <<' ' <<_max;
	fout <<'\n';
    return 0;
}