Cod sursa(job #373330)

Utilizator otilia_sOtilia Stretcu otilia_s Data 13 decembrie 2009 16:05:40
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <deque>
using namespace std;
deque <int> m;
int a[500005];

int main()
{	int i,n,k;
	ifstream fin("secventa.in");
	fin>>n>>k;
	for (i=1;i<=n;++i) fin>>a[i];
	fin.close();
	for (i=1;i<=k;++i)
	{
		if (!m.empty())
			if (a[i]<a[m.front()]) m.erase(m.begin(),m.end());
				else {
						while (a[i]<=a[m.back()]) m.pop_back();						
					 }
		m.push_back(i);
	}
	int MIN,pMIN;
	MIN=a[m.front()]; pMIN=m.front();
	for (i=k+1;i<=n;++i)
	{
		if (a[i]<a[m.front()]) m.erase(m.begin(),m.end());
			else {while (a[i]<=a[m.back()]) m.pop_back();}
		m.push_back(i);
		if (m.front()==i-k) m.pop_front();
		if (a[m.front()]>MIN) {MIN=a[m.front()]; pMIN=m.front();}
	}	
	ofstream fout("secventa.out");
	fout<<pMIN<<" "<<pMIN+k-1<<" "<<MIN;
	fout.close();
	return 0;
}