Cod sursa(job #597852)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 23 iunie 2011 15:27:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
#include<deque>
using namespace std;
int a[500010],n,k;
int inc,sf,baza=-2000000000;
deque <int> D;
int main()
{
	int i;
	ifstream fin("secventa.in");
	fin>>n>>k;
	for(i=1;i<=n;i++)
		fin>>a[i];
	fin.close();
	for(i=1;i<=n;i++)
	{ 
		while( !D.empty() && a[D.back()]>=a[i])
			D.pop_back();
		D.push_back(i);
		if(D.front()==i-k)
			D.pop_front();
		if(i>=k && a[D.front()]>baza)
		{
			baza=a[D.front()];
			inc=i-k+1;
			sf=i;
		}
	}
	ofstream fout("secventa.out");
	while(a[inc-1]>=baza && inc>1)
		inc--;
	fout<<inc<<' '<<sf<<' '<<baza<<"\n";
	fout.close();
	return 0;
}