Cod sursa(job #1643465)

Utilizator pibogaBogdan piboga Data 9 martie 2016 18:56:34
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include<cstring>
using namespace std;

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

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

int main()
{

   fin>>n>>k;


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

    }
    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;
        }

    }
  fout <<a<<' '<<b<<' '<<maxv;



    return 0;
}