Cod sursa(job #1691395)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 18 aprilie 2016 10:49:16
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>

using namespace std;
ifstream f ("secventa.in");
ofstream g ("secventa.out");
int n,k,i,a[500004],u,p,Max,deque1[500004],poz;
int main()
{
    f>>n>>k;
    for (i=1;i<=n;i++)
        f>>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++;
    }
    g<<poz-k+1<<" "<<poz<<" "<<Max;
    return 0;
}