Cod sursa(job #470338)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 13 iulie 2010 12:19:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <fstream>
using namespace std;

int v[500001],dq[500001],st=1,dr=0;

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

inline void s(int x)
{
	if (dq[st]==x)
		st++;
}

void d(int x)
{
	while (v[dq[dr]]>=v[x] && st<=dr)
		dr--;
	dq[++dr]=x;
}

int main()
{
	int n,k,i,x=0,y=0,maxim=-(1<<15);
	in>>n>>k;
	for (i=1;i<k;i++)
	{
		in>>v[i];
		d(i);
	}
	for (;i<=n;i++)
	{
		in>>v[i];
		s(i-k);
		d(i);
		if (v[dq[st]]>maxim)
		{
			maxim=v[dq[st]];
			x=i-k+1;
			y=i;
		}
	}
	out<<x<<" "<<y<<" "<<maxim<<"\n";
	return 0;
}