Cod sursa(job #1691368)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 18 aprilie 2016 09:29:15
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <cstring>
using namespace std;
int n,k,i,a[500004],u,p,Max,deque1[500004],poz,x,nr;
char s[10000004];
bool ok;
int main()
{
    freopen ("secventa.in","r",stdin);
    freopen ("secventa.out","w",stdout);
    scanf ("%d %d\n", &n, &k);
    gets(s);
    for (i=0;i<=strlen(s);i++)
    {
        x=0;
        ok=false;
        while ((s[i]>='0' && s[i]<='9') || s[i]=='-')
        {
            if (s[i]!='-')
                x=x*10+s[i]-'0';
            else
                ok=true;
            i++;
        }
        if (ok==true)
            x*=-1;
        a[++nr]=x;
    }
    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++;
    }
    printf ("%d %d %d", poz-k+1, poz, Max);
    return 0;
}