Cod sursa(job #1639815)

Utilizator bob123bobelus bob bob123 Data 8 martie 2016 14:07:08
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");
char s[2000006];
int l,ok,t,in,sf,nr,j,Max,Front,Back,n,k,i,a[500001],dq[500001];
int get()
{
    int x=0;ok=0;
    if(s[t]=='-') ok=1;
    while(s[t]!=' '&&s[t]!='\n')
            x=x*10+s[t]-'0',++t;
    if(ok==1)
        x=x*-1;
    ++t;
    return x;
}
int main()
{
    f>>n>>k;
    Front=1;Back=0;f.get();
    f.getline(s,2000000);l=strlen(s);
    for(i=0;i<l;i++)
    {
        if(s[i]==' ')
        {
            if(ok==1)
                a[++j]=-nr;
            else
                a[++j]=nr;
            nr=0; ok=0;
        }
        else
        if(s[i]=='-')ok=1;
        else
            nr=nr*10+s[i]-'0';
    }
    if(ok==1)a[n]=-nr;else a[n]=nr;
    Max=-10000000;
    for(i=1;i<=n;++i){
        while(Front<=Back&&a[i]<a[dq[Back]])
            --Back;
        dq[++Back]=i;
        if(dq[Front]==i-k)
            ++Front;
        if(a[dq[Front]]>Max&&i>=k)
            {
                Max=a[dq[Front]];
                in=i-k+1;
                sf=i;
            }
    }
    g<<in<<" "<<sf<<" "<<Max;
    return 0;
}