Cod sursa(job #1687523)

Utilizator pibogaBogdan piboga Data 12 aprilie 2016 21:49:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

using namespace std;

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

int n,k,u,p,v[500005],deq[500005],i,maxv=-30001,a,b,sgn,j,x;
char c[3000010];

int main()
{
    //freopen ("secventa.in","r",stdin);
   // freopen("secventa.out","w",stdout);
    //scanf("%d",&n);
   // scanf("%d",&k);

    fin >> n >> k;

    fin.get();
    fin.get(c,3000010);

    for (i=1, j=0; i<=n ; i++ , j++)
    {
        if (c[j]=='-')
        {
            sgn=-1;
            j++;
        }
        else
        {
            sgn=1;
        }
        while (c[j]>='0' && c[j]<='9')
        {
            x=x*10+(c[j]-'0');
            ++j;
        }
        v[i]=x;
        x=0;

    }

    for (i=1;i<=n;++i)
    {
        while (p<=u && v[i]<v[deq[u]])
        {
            --u;
        }

        deq[++u]=i;

        if (deq[p]==i-k)
            ++p;

        if (i>=k && v[deq[p]] >  maxv)
        {
                maxv=v[deq[p]];
                a=i-k+1;
                b=i;
        }

    }
  //  printf("%d","%d","%d",a,b,maxv) ;
    fout << a << ' ' << b <<' ' << maxv;


    return 0;
}