Cod sursa(job #812171)

Utilizator mariacMaria Constantin mariac Data 13 noiembrie 2012 16:13:23
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include<fstream>
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");
int v[500001],dq[500001];
int main()
{   int max,pf=0,pi=0;
	int n,k,i;
	fin>>n>>k;
	max=-32000;
	dq[0]=0;
	int p,u;
	p=1;u=0;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
		while(p<=u&&v[i]<=v[dq[u]])u--;
		dq[++u]=i;
		
		if(i-dq[p]>=k)p++;
		
		if(i>=k&&v[dq[p]]>max)
		{	
			max=v[dq[p]];
			pi=dq[p-1]+1;
			pf=i;
		}
	}
	fout<<pi<<" "<<pf<<" "<<max;
	return 0;
}