Cod sursa(job #1691397)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 18 aprilie 2016 10:56:05
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("secventa.in");
ofstream g ("secventa.out");
int n,k,i,a[500004],u,p,Max,deque1[500004],poz,nr,r;
char s[10000004],x;
bool ok;
int main()
{
    f>>n>>k>>x;
    f.getline(s,10000004);
    for (i=0;i<strlen(s);i++)
    {
        ok=false;
        nr=0;
        while ((s[i]>='0' && s[i]<='9') || s[i]=='-')
        {
            if (s[i]=='-')
                ok=true;
            nr=nr*10+s[i]-'0';
            i++;
        }
        if (ok==true)
            a[++r]=-nr;
        else
            a[++r]=nr;
    }
    u=0;
    p=1;
    Max=-30001;
    for (i=1;i<k;i++)
    {
        while (a[i]<a[deque1[u]] && u>=p)
            u--;
        deque1[++u]=i;
    }
    for (i=k;i<=n;i++)
    {
        while (a[i]<a[deque1[u]] && u>=p)
            u--;
        deque1[++u]=i;
        if (a[deque1[p]]>Max)
        {
            Max=a[deque1[p]];
            poz=i;
        }
        if (deque1[p]==(i-k+1))
            p++;
    }
    g<<poz-k+1<<" "<<poz<<" "<<Max;
    return 0;
}