Cod sursa(job #601830)

Utilizator dacyanMujdar Dacian dacyan Data 7 iulie 2011 23:21:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <deque>
#define DIM 500001
#define INF 0x3f3f3f3f
using namespace std;

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

deque<int> Q;
long long sol, n, k;
int a[DIM];
int mx(-INF), cap, coada;


int main()
{
	fin >> n >> k;
	for (int i = 1; i <= n; ++i)
		fin >> a[i];
	
	for (int i = 1; i <= n; ++i)
	{
		while (!Q.empty() && a[i] <= a[Q.back()])
			Q.pop_back();
		Q.push_back(i); 
		
		if (Q.front() == i - k) Q.pop_front();
		
		if (i < k) continue;
		if (a[Q.front()] > mx) 
		{
			mx = a[Q.front()];
			cap = i;
			coada = i - k + 1;
		}
	}
	fout  << coada << ' ' << cap << ' ' << mx << '\n';
	fin.close();
	fout.close();
	return 0;
}