Cod sursa(job #374571)

Utilizator adrian_manducadrian manduc adrian_manduc Data 17 decembrie 2009 14:17:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<iostream>
#include<fstream>
using namespace std;
const int N=3500000;
ifstream f("secventa.in");
ofstream g("secventa.out");
int dq[500001];
int v[500001];
int n,k,i,st,dr;
char t[N];
inline void stanga(int i)
{
	if(dq[st]==i-k)
		++st;
}
void dreapta(int i)
{
	while (st<=dr&&v[i] <= v[dq[dr]] )
		--dr;
	dq[++dr]=i;
}
int main()
{	
	f>>n>>k>>ws;
	int i1,i2,semn=1,x=0,nr=0,max=0;
	st=1; dr=0;
	f.getline(t,N);
	for(i=0; t[i]&&t[i]!='\n';++i)
	{
		if(t[i]=='-')
		{
			semn=-1;
			continue;
		}
		if(t[i]==' ')
		{
			v[++nr]=x*semn;
			x=0;semn=1;
			continue;
		}
		x=x*10+t[i]-'0';
	}
	if(nr!=n)
		v[++nr]=x*semn;
	for(i=1; i<=k; i++)
		dreapta(i);
	i2=k;
	i1=1;
	max=v[dq[st]];
	for(i=k+1; i<=n; i++)
	{
		stanga(i);
		dreapta(i);
		if (v[dq[st]]>max)
		{
			max=v[dq[st]];
			i2=i;
			i1=i-k+1;
		}
	}
	g<<i1<<" "<<i2<<" "<<max;
	return 0;
}