Cod sursa(job #403697)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 25 februarie 2010 10:43:11
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<string.h>
#include<deque>
#define Nmx 500002

using namespace std;

int n,k,a[Nmx],t;
deque <int> D;
char c[Nmx/10000*Nmx];


void citire()
{
    int i,nr=0,ok=1;
	scanf ("%d%d\n",&n,&k);
	gets(c);
	t=strlen (c);
	n=0;
	for (i=0; i<t; ++i)
		if (c[i]>='0'&&c[i]<='9')
			nr=nr*10+c[i]-'0';
		else if (c[i]=='-')
			ok=-1;
		else
		{
			a[++n]=nr*ok;
			nr=0;
			ok=1;
		}
	if (nr)
		a[++n]=nr;
}


void solve()
{
    int max=-5000213,pz;
    for(int i=1;i<=n;++i)
    {
        while(D.size()>0&&D.back()>a[i])
            D.pop_back();
        D.push_back(a[i]);
        if(i>=k)
        {
            if(i>k)
                if(D.front()==a[i-k])
                    D.pop_front();
            if(max<D.front())
            {
                max=D.front();
                pz=i;
            }
        }
    }
    printf("%d %d %d\n",pz-k+1,pz,max);
}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    citire();
    solve();
    return 0;
}