Cod sursa(job #711994)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 12 martie 2012 22:21:41
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
# include <fstream>
# include <deque>
# define NN 500005
using namespace std;
int n, v[NN], inceput, sfarsit, bazamax=-NN, k;
void f_deque()
{
	deque<int>dq;
	int i;
	dq.push_back(1);
	for(i=2;i<k;++i)
	{
		while(!dq.empty() && v[dq.back()]>=v[i])
            dq.pop_back();
        dq.push_back(i);
	}
	for(i=k;i<=n;++i)
	{
		while (!dq.empty() && v[dq.back()]>=v[i])
            dq.pop_back();
        dq.push_back(i);
		if (v[dq.front()]>bazamax)
			bazamax=v[dq.front()], inceput=i-k+1, sfarsit=i;
		if (dq.front()<i-k+2)
			dq.pop_front();
	}
}

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