Cod sursa(job #2098197)

Utilizator LauraNaduLaura Nadu LauraNadu Data 2 ianuarie 2018 15:39:28
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int n, p, u, d[500004], imax, maxim, k, a[500004], i;
char s[3500000];
int main()
{
    f>>n>>k;
    f.get();
    f.get(s, 3500000);
    while(s[i]!=0)
    {
        int semn=1;
        if(s[i]=='-')
        {
            semn=-1;
            i++;
        }
        int nr=0;
        while(s[i]<='9' && s[i]>='0')
        {
            nr=nr*10+(s[i]-'0');
            i++;
        }
        nr*=semn;
        a[++p]=nr;
        if(s[i]==' ')
            i++;
    }
    /*for(i=1;i<=n;i++)
        g<<a[i]<<" ";*/
    p=u=d[1]=1;
    maxim=-30005;
    for(i=2;i<=n;i++)
    {
        while(p<=u && a[i]<a[d[u]])
            u--;
        d[++u]=i;
        if(i-d[p]==k)
            p++;
        if(i>=k)
        {
            if(a[d[p]]>maxim)
            {
                maxim=a[d[p]];
                imax=i;
            }
            //g<<" "<<a[d[p]];<<"\n"
        }
    }
    g<<imax-k+1<<" "<<imax<<" "<<maxim<<"\n";
    return 0;
}