Cod sursa(job #2072101)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 21 noiembrie 2017 13:18:43
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;
int n,k,a[500000],COADA[500000],i,p,u,Max,prim,ult;
ifstream f ("secventa.in");
ofstream g ("secventa.out");
int main()
{
    f>>n>>k>>a[1];
    COADA[1]=1;
    p=u=1;
    for (i=2;i<=k;i++)
    {
        f>>a[i];
        if (a[i]<a[COADA[1]])
        {
            COADA[1]=i;
        }
    }
    for (i=k+1;i<=n;i++)
    {
        f>>a[i];
        if (i-COADA[p]==k)
        {
            p++;
            while (a[COADA[u]]>a[i] && u>p)
            {
                u--;
            }
            u++;
            COADA[u]=i;
        }
        else
        {
            while (a[COADA[u]]>a[i] && u>p)
            {
                u--;
            }
            u++;
            COADA[u]=i;
        }
    }
    Max=a[COADA[1]];
    prim=COADA[1];
    ult=prim+k-1;
    for (i=2;i<=u;i++)
    {
        if (a[COADA[i]]>Max && COADA[i]+k-1<=n)
        {
            Max=a[COADA[i]];
            prim=COADA[i];
            ult=COADA[i]+k-1;
        }
    }
    g<<prim<<" "<<ult<<" "<<Max<<'\n';
    return 0;
}