Cod sursa(job #711997)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 12 martie 2012 22:23:54
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 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);

        start = dq.front();

		if (v[start]>bazamax)
			bazamax=v[start], inceput=i-k+1, sfarsit=i;

		if (start<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;
}