Cod sursa(job #453511)

Utilizator bora_marianBora marian bora_marian Data 11 mai 2010 01:03:10
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<fstream>
using namespace std;
int v[500005],k,sol=-30003,n,ptst,ptdr,aj;
void deque();
int main()
{
	ifstream fin("secventa.in");
	ofstream fout("secventa.out");
	fin>>n>>k;
	int i;
	for(i=1;i<=n;i++)
		fin>>v[i];
	deque();
	fout<<ptst<<" "<<ptdr<<" "<<sol;
	return 0;
}
void deque()
{
	int dq[500005],st,dr,i;
	st=1,dr=1;
	dq[1]=1;
	for(i=2;i<=n;i++)
	{
		while(v[i]<=v[dq[dr]] && dr>=st)
			dr--;
		dq[++dr]=i;
		if(i>=k && v[dq[st]]>sol)
			sol=v[dq[st]],ptst=i-k+1,ptdr=i;
		if(dq[st]<=i-k+1)
			st++;
	}
}