Cod sursa(job #712011)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 12 martie 2012 22:33:20
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
# include <fstream>
# define NN 500005
using namespace std;
int n, v[NN], inceput, sfarsit, bazamax=-NN, k;
void deque()
{
	int dq[NN], st, dr,i;
	st=dr=1;
	dq[st]=1;
	for(i=2;i<k;++i)
	{
		while(v[dq[dr]]>=v[i] && dr>=st)--dr;
		dq[++dr]=i;
	}
	for(i=k;i<=n;++i)
	{
		while (v[dq[dr]]>=v[i] && dr>=st)--dr;
		dq[++dr]=i;
		if (v[dq[st]]>bazamax)
			bazamax=v[dq[st]], inceput=i-k+1, sfarsit=i;
		if (dq[st]<i-k+2)
			++st;
	}
}

int main ()
{
	ifstream fin ("secventa.in");
	fin>>n>>k;
	for (int i=1;i<=n;i++)
		fin>>v[i];
	deque();
	FILE *fout=fopen("secventa.out","w");
    fprintf(fout,"%d %d %d",inceput,sfarsit,bazamax);
	return 0;
}