Cod sursa(job #448950)

Utilizator loginLogin Iustin Anca login Data 5 mai 2010 08:47:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
# include <fstream>
# include <iostream>
# define DIM 500003
using namespace std;
int n, v[DIM], pst, pdr, sol=-DIM, k;

void read ()
{
	ifstream fin ("secventa.in");
	fin>>n>>k;
	for (int i=1;i<=n;i++)
		fin>>v[i];
}

void solve ()
{
	int dq[DIM], st, dr;
	st=dr=1;
	dq[st]=1;
	for(int i=2;i<k;++i)
	{
		while(v[dq[dr]]>=v[i] && dr>=st)--dr;
		dq[++dr]=i;
	}
	for(int i=k;i<=n;++i)
	{
		while (v[dq[dr]]>=v[i] && dr>=st)--dr;
		dq[++dr]=i;
		if (v[dq[st]]>sol)
			sol=v[dq[st]], pst=i-k+1, pdr=i;
		if (dq[st]<i-k+2)
			++st;
	}
}

int main ()
{
	read ();
	solve ();
	ofstream fout ("secventa.out");
	fout<<pst<<" "<<pdr<<" "<<sol;
	return 0;
}