Cod sursa(job #509377)

Utilizator soare_cristian16Cristy93 soare_cristian16 Data 10 decembrie 2010 23:02:08
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.48 kb
#include<fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
const int N=500001;
int n,k,v[N],c[N],s,d,in,sf,maxim=-30001;
int main()
{
	int i;
	f>>n>>k;
	for(i=1;i<=n;i++)
		f>>v[i];
	s=1;
	for(i=1;i<=n;i++)
	{
		while(s<=d&&(i-c[d]>=k||v[i]<=v[c[d]]))
			d--;
		c[++d]=i;
		while(s<=d&&i-c[s]>=k)
			s++;
		if(i>=k&&maxim<v[c[s]])
		{
			maxim=v[c[s]];
			in=i-k+1;
			sf=i;
		}
	}
	g<<in<<' '<<sf<<' '<<maxim;
	return 0;
}