Cod sursa(job #980284)

Utilizator t.g.g.tt.g.g.t t.g.g.t Data 4 august 2013 14:50:19
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
using namespace std;

int a[1000005][2],b[500005];
char c[4000000];
long int n,prim,ult,k,pst,psf,baza,n2,semn,l,i,t;
int main()
{
    ifstream fin ("secventa.in");
    ofstream fout("secventa.out");
    fin>>n>>k; fin.getline(c,100);
    fin.getline(c,sizeof(c)); c[strlen(c)]=' ';
        l=strlen(c);
        i=0;
        while (i<l)
        {
            t=0;
            if (c[i]=='-') { semn=-1; ++i;};
            while (c[i]>='0' && c[i]<='9')
                {
                  t=t*10+(int)(c[i]-48);
                  ++i;
                };
            ++i;
            if (semn==-1) t=-t;
            semn=1;
            b[n2]=t;
            ++n2;
        };
    a[0][0]=b[0];a[0][1]=1;
    for (i=1;i<k;i++)
    {
        ult++;
        a[ult][0]=b[i]; a[ult][1]=i+1;
        while ((ult>prim)&&(a[ult][0]<a[ult-1][0]))
        {
            a[ult-1][0]=a[ult][0];
            a[ult-1][1]=a[ult][1];
            ult--;
        }
    }
    pst=1; psf=k; baza=a[0][0];
    for (i=k;i<n;i++)
    {
        if (a[prim][1]<i-k+2)
        {
            prim++;
        }
        ult++;
        a[ult][0]=b[i]; a[ult][1]=i+1;
        while ((ult>prim)&&(a[ult][0]<a[ult-1][0]))
        {
            a[ult-1][0]=a[ult][0];
            a[ult-1][1]=a[ult][1];
            ult--;
        }
        if (baza<a[prim][0])
        {
            baza=a[prim][0];
            pst=i-k+2;
            psf=i+1;
        }

    }
    fout << pst<<" " << psf<<" " << baza;
    fin.close();
    fout.close();

}