Cod sursa(job #2152053)

Utilizator andrei32576Andrei Florea andrei32576 Data 5 martie 2018 10:36:59
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
using namespace std;

int n,k,i,pos,x,maxx,p1,p2,minn;
int v[500002],AI[500002*4+3];
int inf=2000000000;

ifstream f("secventa.in");
ofstream g("secventa.out");

void creare(int nod,int ls,int ld)
{
    if(ls==ld)
    {
        AI[nod]=min(x,AI[nod]);
        return;
    }

    int mij=(ls+ld)/2;
    if(pos<=mij) creare(2*nod,ls,mij);
    else creare(2*nod+1,mij+1,ld);

    AI[nod]=min(AI[nod],min(AI[2*nod],AI[2*nod+1]));

}

void query(int nod,int ls,int ld,int a,int b)
{
    if(a<=ls && ld<=b)
    {
        if(minn>AI[nod])
            minn=AI[nod];
        return;
    }

    int mij=(ls+ld)/2;
    if(a<=mij) query(2*nod,ls,mij,a,b);
    if(b>mij) query(2*nod+1,mij+1,ld,a,b);

}

int main()
{
    f>>n>>k;

    for(i=1;i<=4*n+1;i++)
        AI[i]=inf;

    for(i=1;i<=n;i++)
    {
        f>>v[i];
        pos=i;
        x=v[i];
        creare(1,1,n);
    }

    maxx=-inf;
    for(i=k;i<=n;i++)
    {
        minn=inf;
        query(1,1,n,i-k+1,i);
        if(minn>maxx)
        {
            maxx=minn;
            p1=i-k+1;
            p2=i;
        }
    }
    g<<p1<<" "<<p2<<" "<<maxx;

    f.close();
    g.close();
    return 0;
}