Cod sursa(job #865352)

Utilizator drobertDumitru Robert drobert Data 26 ianuarie 2013 13:10:46
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>

using namespace std;

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


int n,k,i,deque[500005],v[500005],j,nr,semn;
int front=1,back,maximul=-999999,st,dr;
char s[5000005];

int main ()
{
	f>>n>>k;
	f.get();
	f.get(s,5000005);
	for (i=0;s[i];i++)
	{
		if (s[i]>='0' && s[i]<='9')
		{
			nr=nr*10+s[i]-'0';
			continue;
		}
		if (s[i]=='-')
		{
			semn=1;
			continue;
		}
		if (s[i]==' ')
		{
			if (semn==1)
				nr*=-1;
			semn=0;
			v[++v[0]]=nr;
			nr=0;
		}
	}
	if (semn==1)
		nr*=-1;
	semn=0;
	v[++v[0]]=nr;
	nr=0;
	for (i=1;i<=n;i++)
	{
		while (front<=back && v[i]<v[deque[back]])
			back--;
		deque[++back]=i;
		if (deque[front]==i-k)
			front++;
		if (i>=k)
		{
			if (v[deque[front]]>maximul)
			{
				maximul=v[deque[front]];
				st=i-k+1;
				dr=i;
			}
		}
	}
	g<<st<<" "<<dr<<" "<<maximul;
}