Cod sursa(job #516458)

Utilizator crazzytudTudor Popa crazzytud Data 24 decembrie 2010 11:33:47
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>
using namespace std;

const int N=500000;

int d[N],v[N],st,dr,k,i,n;

inline void stanga(int i)
{
	if(i-d[st]==k&&v[d[st]]<=v[d[st+1]])
		st++;
}

inline void dreapta(int i)
{
	while(st<=dr && v[d[dr]]>=v[i])
		dr--;
}

inline void adauga(int i)
{
	d[++dr]=i;
}


ifstream in("secventa.in");
ofstream out("secventa.out");

int main()
{
	in>>n>>k;
	int max=-100000;
	int i1,i2;
	
	
	st=1;dr=0;d[1]=1;
	for (i=1;i<=n;++i)
	{
		in >> v[i];
		
		dreapta(i);
		adauga(i);
		stanga(i);
		
		if (i>=k && v[d[st]]>max)
		{
			max=v[d[st]];
			i1=i-k+1;
			i2=i;
		}
	}
	out<<i1<<" "<<i2<<" "<<max;
	return 0;
}