Cod sursa(job #943947)

Utilizator predatorGigi Valoare predator Data 26 aprilie 2013 20:19:55
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#define NM 500100
#define DIM 4000000
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int A[NM],n,k,i,front,back,D[NM],ma,st,x,j,d,dr;
char s[DIM];
int main()
{
    ma=-900000;
    f.get(s,DIM,EOF);
	while(s[j]<='9'&&s[j]>='0')
		n=n*10+s[j]-'0',j++;
	j++;
	while(s[j]<='9'&&s[j]>='0')
		k=k*10+s[j]-'0',j++;
	j++;
    for(i=1;i<=n;++i)
	{
		x=0;
		if(s[j]=='-')
			d=-1,++j;
		else
			d=1;
		while(s[j]<='9'&&s[j]>='0')
			x=x*10+s[j]-'0',j++;
		j++;
        A[i]=x*d;
	}
    front=1;
    back=0;
    for(i=1;i<=n;++i)
    {
        while(front<=back&&A[i]<=A[D[back]]) D[back]=0,back--;
        D[++back]=i;
        if(D[front]==i-k) front++;
        if(i>=k&&A[D[front]]>ma)
            ma=A[D[front]],st=i-k+1,dr=i;
    }
    g<<st<<" "<<dr<<" "<<ma;
    return 0;
}