Cod sursa(job #597851)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 23 iunie 2011 15:25:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 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(i>=k && a[D.front()]>baza)
		{
			baza=a[D.front()];
			sf=D.front();
		}
		if(D.front()==i-k+1)
			D.pop_front();
	}
	ofstream fout("secventa.out");
	inc=sf;
	while(a[inc-1]>=baza && inc>1)
		inc--;
	fout<<inc<<' '<<max(sf,inc+k-1)<<' '<<baza<<"\n";
	fout.close();
	return 0;
}