Cod sursa(job #1691367)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 18 aprilie 2016 09:16:17
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>

using namespace std;
int n,k,i,a[500004],u,p,Max,deque1[500004],poz;
int main()
{
    freopen ("secventa.in","r",stdin);
    freopen ("secventa.out","w",stdout);
    scanf ("%d %d", &n, &k);
    for (i=1;i<=n;i++)
        scanf ("%d", &a[i]);
    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;
}